Grant: Discovery Grants Program - Individual
University of Waterloo
$29,000.00
Exact linear algebra: nearly optimal algorithms for nonuniform problems
FY 2008-09
Summary
The objective of this research program is to design and analyse new algorithms for the exact solution of problems in the area of linear algebra. Our focus is on problems involving matrices filled with integers and polynomials. The goal is to discover algorithms that make efficient use of computer resources including time (number of required machine word operations) and space (memory requirements).
Fast algorithms for exact linear algebra are a central component of the mathematical engines of computer algebra systems. Computer algebra is very widely used by researchers and practitioners in the mathematical, scientific and engineering communities. Algebraic computations arise in diverse areas such as graphics and robotics. The solutions of complex problems in these areas typically requires the solution of exact linear algebra problems, either as key steps during the computation or, in many cases, as the computational bottleneck. Computational problems involving large integer matrices arise, for example, during the security study of certain types of cryptographic systems. The development of new algorithms that are both rigorously analysed and practically fast is especially welcome. We plan to implement prototypes of the algorithms we design and use them to solve large problems occurring in practice.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
262082-2007
Name nom
Storjohann, Arne
Department département
Computer Science, School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2007
Award amount
29000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Exact linear algebra: nearly optimal algorithms for nonuniform problems
Keyword
NA
Application summary
The objective of this research program is to design and analyse new algorithms for the exact solution of problems in the area of linear algebra. Our focus is on problems involving matrices filled with integers and polynomials. The goal is to discover algorithms that make efficient use of computer resources including time (number of required machine word operations) and space (memory requirements).
Fast algorithms for exact linear algebra are a central component of the mathematical engines of computer algebra systems. Computer algebra is very widely used by researchers and practitioners in the mathematical, scientific and engineering communities. Algebraic computations arise in diverse areas such as graphics and robotics. The solutions of complex problems in these areas typically requires the solution of exact linear algebra problems, either as key steps during the computation or, in many cases, as the computational bottleneck. Computational problems involving large integer matrices arise, for example, during the security study of certain types of cryptographic systems. The development of new algorithms that are both rigorously analysed and practically fast is especially welcome. We plan to implement prototypes of the algorithms we design and use them to solve large problems occurring in practice.