Algorithms for exact linear algebra

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

Computer algebra systems such as Maple, Mathematica, Magma, and more recently SAGE, have become essential tools for mathematicians, computer scientists and educators. These systems allow computations with exact arithmetic on symbolic inputs over a wide variety of domains, for example integers and polynomials. My research focus is primarily on problems involving matrices with integer and polynomial entries. Computations with integer and polynomial matrices occur frequently in diverse areas such as cryptography and linear systems theory. The primary objective of the research is to discover improved algorithms for transforming matrices to certain "normal forms" which naturally reveal the structure and information that is encoded in the rows and columns of the matrix. The goal is to achieve algorithms which are nearly optimal in terms of the number of required bit operations. The algorithms developed will be space-efficient, using no more intermediate space than required to write down the input and output. A challenge in this work is to design algorithms that correctly handle the exact domains of computation. For example, the sizes (number of digits) of integers need to be taken into account in the design and analysis of algorithms, especially since integers arising during the computation and appearing in the output can be much larger than those in the input matrix. The long term goal is a portable software library, based on the novel techniques and algorithms arising from the research, for doing exact linear algebra computations with integer and polynomial matrices. The algorithms arising from the research will allow the solution of larger linear algebra problems, and will make more effective use of computer resources.