On the complexity of polynomial matrix computations

ABSTRACT

We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we mean ntimes n matrices in K[x] of degree bounded by d, with K a commutative field. Under the straight-line program model we show that multiplication is reducible to the problem of computing the coefficient of degree d of the determinant. Conversely, we propose algorithms for minimal approximant computation and column reduction that are based on polynomial matrix multiplication; for the determinant, the straight-line program we give also relies on matrix product over K[x] and provides an alternative to the determinant algorithm of [16, 17]. We further show that all these problems can be solved in particular in O (^ω) operations in K. Here the "soft O" notation O indicates some missing log (nd) factors and ω is the exponent of matrix multiplication over K.

REFERENCES

• 1: W. Baur and V. Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22:317--330, 1983.
• 2: Bernhard Beckermann , George Labahn, A Uniform Approach for the Fast Computation of Matrix-Type Pade Approximants, SIAM Journal on Matrix Analysis and Applications, v.15 n.3, p.804-823, July 1994 [doi>10.1137/S0895479892230031]
• 3: Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
• 4: J. Bunch and J. Hopcroft. Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation, 28:231--236, 1974.
• 5: P. Bürgisser, M. Clausen, and M.A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, 1997.
• 6: David G. Cantor , Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, v.28 n.7, p.693-701, Oct. 1991 [doi>10.1007/BF01178683]
• 7: Don Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Mathematics of Computation, v.62 n.205, p.333-350, Jan. 1994 [doi>10.2307/2153413]
• 8: Mark William Giesbrecht, Nearly optimal algorithms for canonical matrix forms, University of Toronto, Toronto, Ont., Canada, 1993
• 9: O.H. Ibarra, S. Moran, and R. Hui. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of Algorithms, 3:45--56, 1982.
• 10: C.-P. Jeannerod and G. Villard. Straight-line computation of the polynomial matrix inverse. Research Report 2002-47, Laboratoire LIP, ENS Lyon, France. http://www.ens-lyon.fr/LIP/Pub/rr2002.html.
• 11: T. Kailath. Linear systems. Prentice Hall, 1980.
• 12: S. Linnainmaa. Taylor expansion of the accumulated rounding errors. BIT, 16:146--160, 1976.
• 13: Austin Anthony Lobo, Matrix-free linear system solving and applications to symbolic computation, Rensselaer Polytechnic Institute, Troy, NY, 1996
• 14: T. Mulders , A. Storjohann, On lattice reduction for polynomial matrices, Journal of Symbolic Computation, v.35 n.4, p.377-401, April 2003 [doi>10.1016/S0747-7171(02)00139-6]
• 15: A. Storjohann. Algorithms for Matrix Canonical Forms. PhD thesis, Institut für Wissenschaftliches Rechnen, ETH-Zentrum, Zurich, Switzerland, November 2000.
• 16: Arne Storjohann, High-order lifting, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.246-254, July 07-10, 2002, Lille, France [doi>10.1145/780506.780538]
• 17: Arne Storjohann, High-order lifting and integrality certification, Journal of Symbolic Computation, v.36 n.3-4, p.613-648, September 2003 [doi>10.1016/S0747-7171(03)00097-X]
• 18: V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354--356, 1969.
• 19: V. Strassen. Vermeidung von Divisionen. J. Reine Angew. Math., 264:182--202, 1973.
• 20: Emmanuel Thomé, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Journal of Symbolic Computation, v.33 n.5, p.757-775, May 2002 [doi>10.1006/jsco.2002.0533]
• 21: William Jonathan Turner , Erich Kaltofen, Black box linear algebra with the linbox library, 2002
• 22: G. Villard. Computation of the inverse and determinant of a matrix. Algorithms Seminar 2001 - 2002, F. Chyzak, editor. INRIA Rocquencourt, France, 2003.
• 23: G. Villard, Computing Popov and Hermite forms of polynomial matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.250-258, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.237082]
• 24: G. Villard, Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.32-39, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258742]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms

Keywords:
column reduced form, determinant, matrix gcd, matrix polynomial, minimal basis, polynomial matrix multiplication