The schur aggregation for solving linear systems of equations

ABSTRACT

According to our previous theoretical and experimental study, additive preconditioners can be readily computed for ill conditioned matrices, but application of such preconditioners to facilitating matrix computations is not straight-forward. In the present paper we develop some nontrivial techniques for this task.They enabled us to con ne the original numerical problems to the computation of the Schur aggregates of smaller sizes. We overcome these problems by extending the Wilkinson's iterative re nement and applying some advanced semi-symbolic algorithms for multiplication and summation.In particular with these techniques we control precision throughout our computations.

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: 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]
• 3: T. J. Dekker, A Floating-point Technique for Extending the Available Precision, Numerische Mathematik, 18 224--242, 1971.
• 4: J. D. Dixon, Exact Solution of Linear Equations Using p-adic Expansions, Numerische Math., 40 137--141, 1982.
• 5: Jack J. Dongarra , Lain S. Duff , Danny C. Sorensen , Henk A. Vander Vorst, Numerical Linear Algebra for High Performance Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 6: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 7: James Demmel , Yozo Hida, Accurate and Efficient Floating Point Summation, SIAM Journal on Scientific Computing, v.25 n.4, p.1214-1248, 2003 [doi>10.1137/S1064827502407627]
• 8: Ioannis Z. Emiris , Victor Y. Pan , Yanqiang Yu, Modular arithmetic for linear algebra computations in the real field, Journal of Symbolic Computation, v.26 n.1, p.71-87, July 1998 [doi>10.1006/jsco.1998.0201]
• 9: Agner Fog, How to Optimize for the Pentium Family of Microprocessors, www.agner.org, 1996-2004, last updated 2004-04-16.
• 10: G. H. Golub, Some Modified Matrix Eigenvalue Problems, SIAM Review, 15 318--334, 1973.
• 11: J. R. Gilbert, H. Hafsteinsson, Parallel Symbolic Factorization of Sparse Linear Systems, Parallel Computing, 14 151--162, 1990.
• 12: W. Gautschi, G. Inglese, Lower Bounds for the Condition Number of Vandermonde Matrices, Numerische Math., 52 241--250, 1988.
• 13: I. Gohberg , T. Kailath , V. Olshevsky, Fast Gaussian elimination with partial pivoting for matrices with displacement structure, Mathematics of Computation, v.64 n.212, p.1557-1576, Oct. 1995 [doi>10.2307/2153371]
• 14: I. Gohberg, V. Olshevsky, Complexity of Multiplication with Vectors for Structured Matrices, Linear Algebra and Its Applications, 202 163--192, 1994.
• 15: John R. Gilbert , Robert Schreiber, Highly parallel sparse Cholesky factorization, SIAM Journal on Scientific and Statistical Computing, v.13 n.5, p.1151-1172, Sept. 1992 [doi>10.1137/0913067]
• 16: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 17: G. Heinig, Inversion of Generalized Cauchy Matrices and the Other Classes of Structured Matrices, Linear Algebra for Sigmal Processing, IMA Volume in Math. and Its Applications, 69 95--114, 1995.
• 18: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 19: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 20: IA-32 Intel Architecture Software Developer's Manual, Volume 1: Basic Architecture, (Order Number 245470) Intel Corporation, Mt. Prospect, Illinois, 2001.
• 21: I. Kaporin, A Practical Algorithm for Faster Matrix Multiplication, Numerical Linear Algebra with Applications, 6, 8 687--700, 1999.
• 22: 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]
• 23: Xiaoye S. Li , James W. Demmel , David H. Bailey , Greg Henry , Yozo Hida , Jimmy Iskandar , William Kahan , Suh Y. Kang , Anil Kapur , Michael C. Martin , Brandon J. Thompson , Teresa Tung , Daniel J. Yoo, Design, implementation and testing of extended and mixed precision BLAS, ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.152-205, June 2002 [doi>10.1145/567806.567808]
• 24: 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.
• 25: R. J. Lipton, D. Rose, R. E. Tarjan, Generalized Nested Dissection, SIAM J. on Numerical Analysis, 162 346--358, 1979.
• 26: Robert T. Moenck , John H. Carter, Approximate algorithms to derive exact solutions to systems of linear equations, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.65-73, June 01, 1979
• 27: W. L. Miranker, V. Y. Pan, Methods of Aggregations, Linear Algebra and Its Applications, 29 231--257, 1980.
• 28: Takeshi Ogita , Siegfried M. Rump , Shin'ichi Oishi, Accurate Sum and Dot Product, SIAM Journal on Scientific Computing, v.26 n.6, p.1955-1988, 2005 [doi>10.1137/030601818]
• 29: Victor Pan, How can we speed up matrix multiplication?, SIAM Review, v.26 n.3, p.393-415, July 1984 [doi>10.1137/1026076]
• 30: V. Y. Pan,On Computations with Dense Structured Matrices, Math. of Computation, 55, 191 179--190, 1990.
• 31: V. Y. Pan, Can We Utilize the Cancelation of the Most Significant Digits? Tech. Report TR 92 061, The International Computer Science Institute, Berkeley, California, 1992.
• 32: Victor Y. Pan, Structured matrices and polynomials: unified superfast algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 33: 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.
• 34: 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.
• 35: 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.
• 36: 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.
• 37: 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, April 2007.
• 38: V. Y. Pan, M. Kunin, R. Rosholt, H. Kodal, Homotopic Residual Correction Processes, Math. of Computation, 75 345--368, 2006.
• 39: 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.
• 40: V. Y. Pan, B. Murphy, G. Qian, R. E. Rosholt, I. Taj-Eddin, Numerical Computation of Determinants with Additive Preconditioning, Technical Report TR 2007011, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, April 2007.
• 41: Victor Pan , John Reif, Fast and efficient parallel solution of sparse linear systems, SIAM Journal on Computing, v.22 n.6, p.1227-1250, Dec. 1993 [doi>10.1137/0222073]
• 42: Victor Pan , Robert Schreiber, An improved Newton interaction for the generalized inverse of a Matrix, with applications, SIAM Journal on Scientific and Statistical Computing, v.12 n.5, p.1109-1130, Sept. 1991 [doi>10.1137/0912058]
• 43: V. Y. Pan, X. Yan, Null Space and Eigenspace Computations with Additive Preprocessing, in these proceedings.
• 44: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 45: G. W. Stewart, Matrix Algorithms, Vol I: Basic Decompositions, SIAM, Philadelphia, 1998.
• 46: G. W. Stewart, Matrix algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 47: E. E. Tyrtyshnikov, How Bad Are Hankel Matrices? Numerische Math., 67, 2, 261--269, 1994.
• 48: H. A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, Cambridge, England, 2003.
• 49: R. Vandebril, M. Van Barel, G. Golub, N. Mastronardi, A Bibliography on Semiseparable Matrices, Calcolo, 42, 3-4, 249--270, 2005.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms

Keywords:
Iterative Refinement, additive preconditioning, linear systems, schur aggregates