Matrix computations and polynomial root-finding with preprocessing
详细信息 查看全文
- 作者：Victor Y. Pan ; Guoliang Qian ; Ai-Long Zheng ; Zhao Chen
- 关键词：Linear systems of equations ; Randomized preprocessing ; Eigen-solving ; Polynomial equation ; Secular equation
- 刊名：Linear Algebra and its Applications
- 出版年：2011
- 出版时间：15 February 2011
- 年：2011
- 卷：434
- 期：4
- 页码：854-879
- 全文大小：371 K
文摘
Solution of homogeneous linear systems of equations is a basic operation of matrix computations. The customary algorithms rely on pivoting, orthogonalization and SVD, but we employ randomized preprocessing instead. This enables us to accelerate the solution dramatically, both in terms of the estimated arithmetic cost and the observed CPU time. The approach is effective in the cases of both general and structured input matrices and we extend it and its computational advantages to the solution of nonhomogeneous linear systems of equations, matrix eigen-solving, the solution of polynomial and secular equations, and approximation of a matrix by a nearby matrix that has a smaller rank or a fixed structure (e.g., of the Toeplitz or Hankel type). Our analysis and extensive experiments show the power of the presented algorithms.