Reliable Krylov-based algorithms for matrix null space and rank

ABSTRACT

Krylov-based algorithms have recently been used, in combination with other methods, to solve systems of linear equations and to perform related matrix computations over finite fields. For example, large and sparse systems of linear equations ;_2; are formed during the use of the number field sieve for integer factorization, and elements of the null space of these systems are sampled.Two rather different kinds of block algorithms have recently been considered. Block Wiedemann algorithms have now been presented and fully analyzed. Block Lanczos algorithms were proposed earlier but are not yet as well understood. In particular, proofs of reliability of block Lanczos algorithms are not yet available. Nevertheless, an examination of the computational number theory literature suggests that block Lanczos algorithms continue to be preferred.This report presents a block Lanczos algorithm that is somewhat simpler than block algorithms that are presently in use and provably reliable for computations over large fields. To my knowledge, this is the first block Lanczos algorithm for which a proof of reliability is available.A different Krylov-based approach is considered for computations over small fields: It is shown that if Wiedemann's sparse matrix preconditioner is applied to an arbitrary matrix then the number of nontrivial invariant factors of the result is, with high probability, quite small. A Krylov-based algorithm to compute a partial Frobenius decomposition can then be used to sample from the null space of the original matrix or to compute its rank. This yields a randomized (Monte Carlo) black box algorithm for matrix rank that is asymptotically faster, in the small field case, than any other that is presently known.

REFERENCES

• 1: J. P. Buhler, H. W. Lenstra, Jr, and C. Pomerance. Factoring integers with the number field sieve. In The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, pages 50--94. Springer-Verlag, 1993.
• 2: L. Chen, W. Eberly, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard. Efficient matrix preconditioners for black box linear algebra. Linear Algebra and Its Applications, 343--344:119--146, 2002.
• 3: D. Coppersmith. Solving linear equations over GF(2): Block Lanczos algorithm. Linear Algebra and Its Applications, 192:33--60, 1993.
• 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: Wayne Eberly, Black box Frobenius decompositions over small fields, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.106-113, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345596]
• 6: W. Eberly. Asymptotically efficient algorithms for the Frobenius form. Technical Report 2003-723-26, Department of Computer Science, University of Calgary, 2003. Available at www.cpsc.ucalgary.ca/~eberly/Publications/.
• 7: Wayne Eberly, Early termination over small fields, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.80-87, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860882]
• 8: W. Eberly. Reliable Krylov-based algorithms for matrix null space and rank. Technical Report 2004-749-14, Department of Computer Science, University of Calgary, 2004. Available at www.cpsc.ucalgary.ca/~eberly/Publications/.
• 9: Wayne Eberly , Erich Kaltofen, On randomized Lanczos algorithms, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.176-183, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258776]
• 10: F. R. Gantmacher. The Theory of Matrices, volume one. Chelsea Publishing Company, second edition, 1959.
• 11: Erich Kaltofen, Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.195-212, May 10-14, 1993
• 12: E. Kaltofen and G. Villard. On the complexity of computing determinants. Research Report 36, Laboratoire de 'Informatique du Parallélisme, Ecole Normale Supérieure de Lyon, France. Available at www.ens-lyon.fr/LIP/Pub/rr2003.html, 2003.
• 13: Brian A. LaMacchia , Andrew M. Odlyzko, Solving Large Sparse Linear Systems over Finite Fields, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.109-133, August 11-15, 1990
• 14: C. Lanczos. Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bureau of Standards, 49:33--53, 1952.
• 15: P. Montgomery. A block Lanczos algorithm for finding dependencies over GF(2). In EUROCRYPT '95, volume 921 of Lecture Notes in Computer Science, pages 106--120. Springer-Verlag, 1995.
• 16: 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]
• 17: 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]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices; Computations in finite fields

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Reliability, Theory

Keywords:
Frobenius decomposition, black box matrix, block lanczos algorithm, linear system solution, matrix rank, randomized algorithm