Unified Nearly Optimal Algorithms for Structured Integer Matrices
Victor Ya. Pan, Brian J. Murphy, Rhys Eric Rosholt · Birkhäuser Basel eBooks · 2010
Our subject is the solution of a structured linear system of equations, which is closely linked to computing a shortest displacement generator for the inverse of its structured coefficient matrix. We consider integer matrices with the displacement structure of Toeplitz, Hankel, Vandermonde, and Cauchy types and combine the unified divide-and-conquer MBA algorithm (due to Morf 1974, 1980 and Bitmead and Anderson 1980) with the Chinese remainder algorithm to solve both computational problems within nearly optimal randomized Boolean and word time bounds. The bounds cover the cost of both solution and its correctness verification. The algorithms and nearly optimal time bounds are extended to the computation of the determinant of a structured integer matrix, its rank and a basis for its null space and further to some fundamental computations with univariate polynomials that have integer coefficients.