Exact linear algebra, polynomial systems and applications of computer algebra

点击翻译按钮获取中文摘要

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.