Computations in linear algebra: a new look at residue arithmetic.

Abstract

The dissertation deals with error-free and approximate computations of some problems in linear algebra, with an emphasis on a modified residue arithmetic developed here. It is divided into five chapters:Chapter 1 The existing residue number systems and their scope are surveyed. Also, a modified residue number system in which each residue number is represented as an ordered pair (mantissa, exponent) and the concerned arithmetic, named here as floating-point modular arithmetic for numbers (FLMAN), are described for error-free computation with rational operands. The division operation in this number system, unlike that in the existing residue number systems, can be carried out even when the denominator of a rational operand or the divisor in a division operation happens to be an integral multiple of one or more moduli. In addition, an algorithm that defines an extended set of Farey fractions, called here generalized Farey fractions, is proposed to convert residue numbers to rational numbers. Chapter 2 The foregoing FLMAN has been extended to rational functions (ratio of two polynomials) in which the elements of the base vector are irreducible polynomials. This arithmetic is called here floating-point modular arithmetic for polynomials (FLMAP). The Lagrange interpolation formula (LIF) is used in place of the Chinese remainder theorem for polynomials. An algorithm for arithmetic on rational polynomials (ARP), including a forward mapping, the FLMAP, the LIF, and an inverse mapping, is presented. Application of the algorithm to matrix processors, specifically the rational matrix (a matrix whose elements are rational functions) inversion based on a division-free procedure and a procedure involving division, is described. Chapter 3 Includes a general algorithm for computing symmetrizers of an arbitrary real nonsymmetric matrix. A special case of the general algorithm valid only for Hessenberg matrices with nonzero codiagonal is presented. A symmetrizer of a matrix A is a matrix X satisfying the matrix equations XA = A?X and X = X?. A symmetrizer is useful in transforming a nonsymmetric eigenvalue problem into a symmetric one. It is shown that there exists no positive definite symmetrizer if the nonsymmetric matrix has complex eigenvalues. In addition, a procedure to compute equivalent symmetric matrices is presented. An equivalent symmetric matrix of a real nonsymmetric matrix is defined here as a real or a complex symmetric matrix whose eigenvalues are the same as those of the nonsymmetric matrix. An implementation of the FLMAN on the general algorithm to compute a matrix symmetrizer exactly is also included. Chapter 4 A matrix T is symmetric Toeplitz if t?? = t|i?j|. If the leading minors of the nonsingular Toeplitz matrix in a symmetric Toeplitz system of equations are zero or near-zero, then most of the algorithms for solving such a system fail or become unstable. An algorithm that uses Zohar's formulation of Trench's algorithm, which is an improvement of Levinson's algorithm, to compute the inverse of a symmetric Toeplitz matrix, where the symmetric Toeplitz matrix can have vanishing or near-vanishing leading minors, is presented. In addition, the conventional single modulus residue arithmetic is superimposed on the foregoing algorithm to compute the exact inverse of a symmetric Toeplitz matrix with vanishing or near-vanishing leading minors. Chapter 5 A polynomial algorithm due to Barnes, which is a variation on Karmarkar's algorithm for linear programming, is studied. The detection of basic variables, based on the monotonic convergence of non-basic variables, as well as the problems involved therein, are discussed.