Error-Free Polynomial Matrix Computations

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-Pade 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.