Grant: Discovery Grants Program - Individual
University of Waterloo
$55,000.00
Exact linear algebra, polynomial systems and applications of computer algebra
FY 2024-25
Summary
Computer algebra systems are vital tools for scientists and engineers. They contain a vast store of mathematical knowledge and provide abilities to manipulate expressions to expand this knowledge using both exact and extended precision numerics. Efficient algorithms in exact arithmetic and correct algorithms in numeric arithmetic are key components in these systems.
This proposal naturally falls into two parts, (1) fast algorithms for symbolic linear algebra and (2) applications of symbolic computation. The second theme is equally divided into (i) algorithms for reduction of invariant polynomial and dynamical systems and (ii) algorithms for determining identities and solutions for multiple definite summation and integration.
In the first part we will pay particular attention to algorithms for faster integer and polynomial matrix arithmetic, something at the heart of modern symbolic computation systems. In particular we will look at matrix normal forms, order bases and their uses for fast matrix polynomial arithmetic along with their applications. As an example, there are computations in algebraic combinatorics which requires fast order basis computation to determine D-finiteness of specific formal power series originating from analysis of algorithms.
Problems and challenges which arise includes linear algebra with matrices or matrix polynomials having parameters, one where the matrix properties change depending on specific values of the parameters. Also matrices of integers or matrices of polynomials, where the growth of coefficient arithmetic is a fundamental concern for efficient algorithms. Finally, while symbolic algorithms typically use exact arithmetic, it is often the case that applications are described in terms of exact algebra but actually work with numeric, floating point coefficients coming from measured data. This is the case, for example, in linear systems theory or control theory, both of which make use of the algebraic formalism of matrix polynomial arithmetic. One then needs to address efficiency and at the same time numerical stability.
The second part of this proposal focuses on the use of computer algebra in applications, particularly those which make significant use of linear or polynomial algebra. In the case of invariant polynomial and dynamical systems we wish to improve the algorithms used to reduce these systems in the presence of symmetries, something which occurs naturally in nature. Specifically one computes invariants and makes use of these to find simpler systems and which in turn provide efficient methods of solving the original systems. In the case of summation and integration, we intend to find new, improved algorithms for constructing reduction algorithms for creative telescoping, a method for finding or verifying summation and definite integration formulas.
Software has always been an important component of our research as it enables one to verify that theory agrees with practice.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2020-04276
Name nom
Labahn, George
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheriton 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
2024
Competition year année de concours
2020
Award amount
55000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
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
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Exact linear algebra, polynomial systems and applications of computer algebra
Keywords
matrix polynomials; reduction of polynomial systems; symbolic/numeric computation; rational function arithmetic; smith and hermite normal forms
Application summary
Computer algebra systems are vital tools for scientists and engineers. They contain a vast store of mathematical knowledge and provide abilities to manipulate expressions to expand this knowledge using both exact and extended precision numerics. Efficient algorithms in exact arithmetic and correct algorithms in numeric arithmetic are key components in these systems.
This proposal naturally falls into two parts, (1) fast algorithms for symbolic linear algebra and (2) applications of symbolic computation. The second theme is equally divided into (i) algorithms for reduction of invariant polynomial and dynamical systems and (ii) algorithms for determining identities and solutions for multiple definite summation and integration.
In the first part we will pay particular attention to algorithms for faster integer and polynomial matrix arithmetic, something at the heart of modern symbolic computation systems. In particular we will look at matrix normal forms, order bases and their uses for fast matrix polynomial arithmetic along with their applications. As an example, there are computations in algebraic combinatorics which requires fast order basis computation to determine D-finiteness of specific formal power series originating from analysis of algorithms.
Problems and challenges which arise includes linear algebra with matrices or matrix polynomials having parameters, one where the matrix properties change depending on specific values of the parameters. Also matrices of integers or matrices of polynomials, where the growth of coefficient arithmetic is a fundamental concern for efficient algorithms. Finally, while symbolic algorithms typically use exact arithmetic, it is often the case that applications are described in terms of exact algebra but actually work with numeric, floating point coefficients coming from measured data. This is the case, for example, in linear systems theory or control theory, both of which make use of the algebraic formalism of matrix polynomial arithmetic. One then needs to address efficiency and at the same time numerical stability.
The second part of this proposal focuses on the use of computer algebra in applications, particularly those which make significant use of linear or polynomial algebra. In the case of invariant polynomial and dynamical systems we wish to improve the algorithms used to reduce these systems in the presence of symmetries, something which occurs naturally in nature. Specifically one computes invariants and makes use of these to find simpler systems and which in turn provide efficient methods of solving the original systems. In the case of summation and integration, we intend to find new, improved algorithms for constructing reduction algorithms for creative telescoping, a method for finding or verifying summation and definite integration formulas.
Software has always been an important component of our research as it enables one to verify that theory agrees with practice.