Wayne Eberly
ABSTRACT
A new block Lanczos algorithm for computations over small finite fields is presented and analysed. The algorithm can be used to solve a system of linear equations or sample uniformly from the null space whenever the number of nilpotent blocks with order at least two in the Jordan form of the given coefficient matrix is less than the block factor on the right. It can also be used to verify that this matrix condition is not satisfied, in order to confirm that preconditioning of the given matrix is required.
- J. P. Buhler, J. H. W. Lenstra, and C. Pomerance. Factoring integers with the number field sieve. In The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Computer Science, pages 50--94. Springer-Verlag, 1993.Google Scholar
Cross Ref
- 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.Google ScholarCross Ref
- D. Coppersmith. Solving linear equations over GF(2): Block Lanczos algorithm. Linear Algebra and Its Applications, 192:33--60, 1993.Google ScholarCross Ref
- W. Eberly. Reliable Krylov-based algorithms for matrix null space and rank. In Proceedings, 2004 International Symposium on Symbolic and Algebraic Computation, pages 127--134, Santander, Spain, 2004. Google ScholarDigital Library
- W. Eberly. Yet another block Lanczos algorithm: How to simplify the computation and reduce reliance on preconditioners in the small field case. Technical Report 2010-957-06, Department of Computer Science, University of Calgary, 2010. Available online at www.cpsc.ucalgary.ca/~eberly/Research/publications.php.Google Scholar
- M. Giesbrecht, A. Lobo, and B. D. Saunders. Certifying inconsistency of sparse linear systems. In Proceedings, 1998 International Symposium on Symbolic and Algebraic Computation, pages 113--119, University of Rostock, Germany, 1998. Google ScholarDigital Library
- B. Hovinen and W. Eberly. A reliable block Lanczos algorithm over small finite fields. In Proceedings, 2005 International Symposium on Symbolic and Algebraic Computation, pages 177--184, Beijing, China, 2005. Google ScholarDigital Library
- P. L. Montgomery. A block Lanczos algorithm for finding dependencies over GF(2). In Advances in Cryptology---EUROCRYPT '95, volume 921 of Lecture Notes in Computer Science, pages 106--120. Springer-Verlag, 1995. Google ScholarDigital Library
- G. Villard. Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems. In Proceedings, 1997 International Symposium on Symbolic and Algebraic Computation, pages 32--39, Maui, Hawaii, 1997. Google ScholarDigital Library
- D. Wiedemann. Solving sparse linear equations over finite fields. IEEE Transactions on Information Theory, IT-32:54--62, 1986. Google ScholarDigital Library
Index Terms
- Yet another block Lanczos algorithm: how to simplify the computation and reduce reliance on preconditioners in the small field case
Recommendations
Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications
Low-rank approximation of large and/or sparse matrices is important in many applications, and the singular value decomposition (SVD) gives the best low-rank approximations with respect to unitarily-invariant norms. In this paper we show that good low-rank ...
A block MINRES algorithm based on the band Lanczos method
We develop a block minimum residual (MINRES) algorithm for symmetric indefinite matrices. This version is built upon the band Lanczos method that generates one basis vector of the block Krylov subspace per iteration rather than a whole block as in the ...
Comments