Null space and eigenspace computations with additive preprocessing

ABSTRACT

We propose and analyze additive preprocessing for computing a vector in the null space of a matrix and a basis for this space. Due to our preprocessing, instead of singular linear systems we solve nonsingular ones, which preserve the conditioning properties and the structure of the input matrices. We extend our preprocessing to decrease the size and the condition number of an ill conditioned input matrix. We also cover applications to the eigenspace computations and to generating effective preconditioners for a linear system of equations.

REFERENCES

• 1: R. Barrett, M. W. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, 1993.
• 2: Zhaojun Bai , James Demmel , Jack Dongarra , Axel Ruhe , Henk van der Vorst, Templates for the solution of algebraic eigenvalue problems: a practical guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 3: D. A. Bini, L. Gemignani, V. Y. Pan, Inverse Power and Durand/Kerner Iteration for Univariate Polynomial Root-finding, Computers and Mathematics (with Applications), 47, 2/3, 447--459, January 2004. (Also Technical Reports TR 2002 003 and 2002 020, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, 2002.)
• 4: D. A. Bini, L. Gemignani, V. Y. Pan, Improved Initialization of the Accelerated and Robust QR-like Polynomial Root-finding, Electronic Transactions on Numerical Analysis, 17, 195--205, 2004.
• 5: Dario A. Bini , Luca Gemignani , Victor Y. Pan, Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations, Numerische Mathematik, v.100 n.3, p.373-408, May 2005 [doi>10.1007/s00211-005-0595-4]
• 6: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 7: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 8: S. Fortune, An Iterated Eigenvalue Algorithm for Approximating Roots of Univariate Polynomials, J. of Symbolic Computation, 33, 5, 627--646, 2002. (Proc. version in Proc. Intern. Symp. on Symbolic and Algebraic Computation (ISSAC'01), 121--128, ACM Press, New York, 2001.)
• 9: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 10: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 11: Ilse C. F. Ipsen, Computing an Eigenvector with Inverse Iteration, SIAM Review, v.39 n.2, p.254-291, June 1997 [doi>10.1137/S0036144596300773]
• 12: I. Kaporin, A Practical Algorithm for Faster Matrix Multiplication, Numerical Linear Algebra with Applications, 6, 8, 687--700, 1999.
• 13: Igor Kaporin, The aggregation and cancellation techniques as a practical tool for faster matrix multiplication, Theoretical Computer Science, v.315 n.2-3, p.469-510, 6 May 2004 [doi>10.1016/j.tcs.2004.01.004]
• 14: J. Laderman, V. Y. Pan, H. X. Sha, On Practical Algorithms for Accelerated Matrix Multiplication, Linear Algebra and Its Applications, 162--164, 557--588, 1992.
• 15: W. L. Miranker, V. Y. Pan, Methods of Aggregations, Linear Algebra and Its Applications, 29, 231--257, 1980.
• 16: F. Malek, R. Vaillancourt, Polynomial Zerofinding Iterative Matrix Algorithms, Computers and Math. (with Applications), 29, 1, 1--13, 1995.
• 17: F. Malek, R. Vaillancourt, A Composite Polynomial Zerofinding Matrix Algorithm, Computers and Math. (with Applications), 30, 2, 37--47, 1995.
• 18: Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 19: Victor Pan, How can we speed up matrix multiplication?, SIAM Review, v.26 n.3, p.393-415, July 1984 [doi>10.1137/1026076]
• 20: Victor Y. Pan, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Review, v.39 n.2, p.187-220, June 1997 [doi>10.1137/S0036144595288554]
• 21: Victor Y. Pan, Structured matrices and polynomials: unified superfast algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 22: V. Y. Pan, On Eigen-solving via Reduction to DPR1 Matrices, preprint, 2007.
• 23: V. Y. Pan, Null Aggregation and Extensions, Technical Report TR 2007009, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, April 2007.
• 24: V. Y. Pan, D. Ivolgin, B. Murphy, R. E. Rosholt, I. Taj-Eddin, Y. Tang, X. Yan, Additive Preconditioning and Aggregation in Matrix Computations, Technical Report TR 2006006, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, May 2006.
• 25: V. Y. Pan, D. Ivolgin, B. Murphy, R. E. Rosholt, Y. Tang, X. Wang, X. Yan, Root-finding with Eigen-solving, pages 219--245 in Symbolic-Numerical Computation, (Dongming Wang and Lihong Zhi editors), Birkhäuser, Basel/Boston, 2007.
• 26: V. Y. Pan, D. Ivolgin, B. Murphy, R. E. Rosholt, Y. Tang, X. Yan, Additive Preconditioning in Matrix Computations, Technical Report TR 2005009, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, July 2005.
• 27: V. Y. Pan, D. Ivolgin, B. Murphy, R. E. Rosholt, Y. Tang, X. Yan, Additive Preconditioning and Aggregation in Matrix Computations, Technical Report TR 2007002, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, March 2007.
• 28: V. Y. Pan, D. Ivolgin, B. Murphy, R. E. Rosholt, Y. Tang, X. Yan, Additive Preconditioning for Matrix Computations, Technical Report TR 2007003, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, March 2007.
• 29: V. Y. Pan, B. Murphy, G. Qian, R. E. Rosholt, Error-free Computations via Floating-Point Operations, Technical Report TR 2007010, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, April 2007.
• 30: V. Y. Pan, B. Murphy, R. E. Rosholt, M. Tabanjeh, The Schur Aggregation for Solving Linear Systems of Equations, in these proceedings.
• 31: V. Y. Pan, X. Yan, Additive Preconditioning, Eigenspaces, and the Inverse Iteration, Technical Report TR 2007004, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, March 2007.
• 32: G. W. Stewart, Matrix Algorithms, Vol I: Basic Decompositions, SIAM, Philadelphia, 1998.
• 33: G. W. Stewart, Matrix algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 34: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 35: Xinmao Wang, Effect of small rank modification on the condition number of a matrix, Computers & Mathematics with Applications, v.54 n.6, p.819-825, September, 2007 [doi>10.1016/j.camwa.2006.05.031]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

General Terms:
Algorithms

Keywords:
additive preprocessing, eigenspace computations, ill conditioned matrices, null space computations