Error-Free Polynomial Matrix Computations

This book is written as an introduction to polynomial matrix computa­ tions. It is a companion volume to an earlier book on Methods and Applications of Error-Free Computation by R. T. Gregory and myself, published by Springer-Verlag, New York, 1984. This book is intended for seniors and graduate students in computer and system sciences, and mathematics, and for researchers in the fields of computer science, numerical analysis, systems theory, and computer algebra. Chapter I introduces the basic concepts of abstract algebra, including power series and polynomials. This chapter is essentially meant for bridging the gap between the abstract algebra and polynomial matrix computations. Chapter II is concerned with the evaluation and interpolation of polynomials. The use of these techniques for exact inversion of poly­ nomial matrices is explained in the light of currently available error-free computation methods. In Chapter III, the principles and practice of Fourier evaluation and interpolation are described. In particular, the application of error-free discrete Fourier transforms for polynomial matrix computations is consi­ dered.

I Algebraic Concepts.- 1 Introduction.- 2 Groups, Rings, Integral Domains, and Fields.- 2.1 Groups.- 2.2 Rings.- 2.3 Integral domain.- 2.4 Unique factorization domain.- 2.5 Euclidean domains.- 2.6 Field F.- 2.7 Use of EEA to compute multiplicative inverse.- 2.8 Additional properties of EEA.- 2.9 Ideals, principal ideals, quotient rings.- 3 Power Series and Polynomials.- 3.1 Formal power series R[[x]].- 3.2 Polynomial rings.- 3.3 Field of quotients.- 3.4 Examples.- 3.5 Division property of F[x].- 3.6 Examples.- 3.7 Congruence properties.- 4 Chinese Remainder Theorem and Interpolation.- 4.1 Chinese remainder theorem.- 4.2 Theorem.- 4.3 Equivalence to Lagrange interpolation.- 4.4 Algorithm for reconstructing r and r(x).- 4.5 Residue representation of signed integers.- 5 Polynomials in Several Variables.- 5.1 Definition.- 5.2 Formal power series.- 5.3 Pseudodivision and remainder theorem.- 5.4 Evaluation-interpolation.- Exercises I.- II Polynomial Matrix―Evaluation, Interpolation, Inversion.- 1 Introduction.- 2 Results from Matrix Theory.- 2.1 Matrices over fields.- 2.2 Matrices over F[x].- 2.3 Elementary transformations.- 2.4 Smith Canonical form.- 2.5 Substitution.- 2.6 Inverse matrix.- 3 Matrix Method―Evaluation and Interpolation of Single Variable Polynomials.- 3.1 Single variable polynomial matrix inversion.- 3.2 Modular method.- 4 Tensor Product Method―Evaluation and Interpolation of Multi-variable Polynomials.- 4.1 Two-dimensional grid evaluation―interpolation.- 4.2 Tensor products and their properties.- 4.3 Use of tensor product for grid evaluation―interpolation.- 4.4 Inversion of multivariable polynomial matrices.- Exercises II.- III Fourier Evaluation and Interpolation.- 1 Introduction.- 2 Discrete Fourier Transform over a Ring.- 2.1 Primitive nth root of unity.- 2.2 Discrete Fourier transform (DFT).- 2.3 Theorem.- 2.4 Inverse discrete Fourier transform (IDFT).- 3 Convolution.- 3.1 Cyclic convolution property (CCP).- 3.2 Remarks.- 4 Error-Free DFT.- 4.1 Basic number theoretic results.- 4.2 Number theoretic transforms (NTT).- 4.3 Mersenne transforms.- 4.4 Fermat and Rader transforms.- 5 Polynomial Evaluation―Interpolation―Multiplication.- 5.1 Single-variable polynomial multiplication.- 5.2 Example.- 5.3 Choice of modulus for computation.- 5.4 Example.- 5.5 Complexity reduction.- 6 Multivariable Polynomial Interpolation.- 6.1 Example.- 6.2 Choice of resulting vector length and coefficient size.- 6.3 Example.- 6.4 Complexity reduction.- 6.5 Example.- Exercises III.- IV Polynomial Hensel Codes.- 1 Introduction.- 2 Hensel Fields.- 2.1 Hensel’s lemma.- 2.2 Bibliographic remarks.- 3 Isomorphic Algebras.- 3.1 Similar algebras.- 3.2 Morphism.- 3.3 Bibliographic remarks.- 3.4 Hensel Codes for rational numbers.- 4 Hensel Codes for Rational Polynomials.- 4.1 Definitions and notation.- 4.2 Forward mapping.- 4.3 Theorem.- 4.4 Theorem.- 4.5 Theorem (Uniqueness of Coding).- 4.6 Hensel Codes.- 4.7 Forward mapping.- 4.8 Inverse mapping.- 5 Arithmetic of Hensel Codes.- 5.1 Complementation/negation.- 5.2 Addition/subtraction.- 5.3 Multiplication.- 5.4 Multiplicative inverse and division.- 5.5 Newton―Hensel―Zassenhaus (NHZ) iterative method.- 5.6 Euclidean algorithm for finding H(p, r, ?(x)-1).- 6 Forward and Inverse Mapping Algorithms.- 6.1 Forward mapping.- 6.2 Inverse mapping―Padé method.- 6.3 Euclidean inverse mapping.- 6.4 Common denominator method.- 7 Direct Solution of Linear Systems and Matrix Inversion.- 7.1 Gaussian elimination (with scaling).- 7.2 Matrix inversion using reduction.- 7.3 Generalized inverses.- 7.4 Generalized inverse by evaluation―interpolation.- 8 Hensel―Newton―Schultz Iterative Matrix Inversion.- 8.1 Theorem.- 8.2 Example.- 8.3 Inversion of matrices in ?(x).- 8.4 Generalized inversion by iteration.- 8.5 Recursive property.- 8.6 Relation to diophantine approximation.- Exercises IV.- V Matrix Computations―Euclidean and Non-Euclidean Domains.- 1 Introduction.- 2 Matrices over Euclidean Domains.- 2.1 Matrices over I.- 2.2 Matrices over R[x].- 3 Matrices over Non-Euclidean Domains.- 4 Multivariable Polynomial Hensel Codes.- 4.1 Hensel Codes.- 4.2 Forward mapping.- 4.3 Inverse mapping.- 4.4 Arithmetic.- 4.5 Inversion of multivariable polynomial matrix―Gaussian elimination.- 4.6 Iterative inversion of a multivariable polynomial matrix.- 4.7 Iterative g-inversion.- Exercises V.