A block Wiedemann rank algorithm

ABSTRACT

This paper makes two contributions to block Wiedemann algorithms. We describe how to compute the minimal generating matrix polynomial using Beckermann and Labahn's Fast Power Hermite-Padé Solver, and we develop a block Monte Carlo method to compute rank of a black box matrix over a large field by extending the Kaltofen-Saunders black box matrix rank algorithm.

REFERENCES

• 1: Bernhard Beckermann and George Labahn (1992). A Uniform Approach for Hermite Padé and Simultaneous Padé Approximants and Their Matrix-Type Generalizations. Numerical Algorithms, 3:451154.
• 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: Li Chen, Wayne Eberly, Erich Kaltofen, B. David Saunders, William J. Turner, and Gilles Villard (2002). Efficient Matrix Preconditioners for Black Box Linear Algebra. Linear Algebra and its Applications, 343--344:119--146. Special issue on Infinite Systems of Linear Equations Finitely Specified, edited by P. Dewilde, V. Olshevsky and A. H. Sayed.
• 4: 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]
• 5: J.-G. Dumas, T. Gautier, M. Giesbrecht, P. Giorgi, B. Hovinen, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard (2002). LinBox: A Generic Library for Exact Linear Algebra. In Arjeh M. Cohen, Xiao-Shan Gao, and Nobuki Takayama, editors, Proceedings of the 2006 International Congress of Mathematical Software. World Scientific.
• 6: Wayne Eberly, Reliable Krylov-based algorithms for matrix null space and rank, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.127-134, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005305]
• 7: Wayne Eberly , Mark Giesbrecht , Pascal Giorgi , Arne Storjohann , Gilles Villard, Solving sparse rational linear systems, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145785]
• 8: Joachim Von Zur Gathen , Jurgen Gerhard, Modern Computer Algebra, Cambridge University Press, New York, NY, 2003
• 9: Pascal Giorgi , Claude-Pierre Jeannerod , Gilles Villard, On the complexity of polynomial matrix computations, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.135-142, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860889]
• 10: Erich Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, v.64 n.210, p.777-806, April 1995 [doi>10.2307/2153451]
• 11: Erich Kaltofen , Victor Pan, Processor efficient parallel solution of linear systems over an abstract field, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.180-191, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113396]
• 12: Erich Kaltofen , B. David Saunders, On Wiedemann's Method of Solving Sparse Linear Systems, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.29-38, October 07-11, 1991
• 13: Erich Kaltofen and Gilles Villard (2001). On the Complexity of Computing Determinants (Extended abstract). In Kiyoshi Shirayanagi and Kazuhiro Yokoyama, editors, Proceedings of the Fifth Asian Symposium on Computer Mathematics (ASCM 2001), volume 9 of Lecture Notes Series on Computing, pages 13--27. World Scientific. Invited contribution.
• 14: Erich Kaltofen , Gilles Villard, On the complexity of computing determinants, Computational Complexity, v.13 n.3-4, p.91-130, February 2005 [doi>10.1007/s00037-004-0185-3]
• 15: V. M. Popov (1970). Some Properties of Control Systems with Irreducible Matrix Transfer Functions. In J. A. Yorke, editor, Seminar on Differential Equations and Dynamical Systems, II, volume 144 of Lecture Notes in Computer Science, pages 169--180. Springer Verlag.
• 16: B. David Saunders, Arne Storjohann, and Gilles Villard (2004). Matrix Rank Certification. Elect. J. Linear Algebra, 11:16--23.
• 17: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 18: William Jonathan Turner , Erich Kaltofen, Black box linear algebra with the linbox library, 2002
• 19: William J. Turner (2003). Determinantal Divisors and Matrix Preconditioners. Submitted to Journal of Symbolic Computation.
• 20: Marc Van Barel and Adhemar Bultheel (1991). The Computation of Non-Perfect Padé-Hermite Approximants. Numerical Algorithms, 1:285--304.
• 21: 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]
• 22: Gilles Villard (1997b). A Study of Coppersmith's Block Wiedemann Algorithm using Matrix Polynomials. Rapport de Recherche 975 IM, Institut d'Informatique et de Mathématiques Appliquées de Grenoble.
• 23: Gilles Villard, Processor efficient parallel solution of linear systems of equations, Journal of Algorithms, v.35 n.1, p.122-126, April 2000 [doi>10.1006/jagm.1999.1069]
• 24: D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]
• 25: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• 26: Richard Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation, v.9 n.3, p.375-403, March 1990 [doi>10.1016/S0747-7171(08)80018-1]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
black box linear algebra, block Wiedemann method, power Hermite-Padé approximation, rank algorithm