Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$55,000.00

Exact linear algebra, polynomial systems and applications of computer algebra

FY 2023-24

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
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
2023
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
9999
Research subject group en
Not available
Research subject group fr
Not available
Research subject en
Non disponible
Research subject fr
Non disponible
Application title
Exact linear algebra, polynomial systems and applications of computer algebra
Keyword
Matrix polynomials; Rational function arithmetic; Reduction of polynomial systems; Smith and Hermite normal forms; Symbolic/Numeric computation
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.