Matrix Condition Number Prediction with SVM Regression and Feature Selection

Shuting Xu, and Jun Zhang
Laboratory for High Performance Scientific Computing and Computer Simulation
Department of Computer Science
University of Kentucky
Lexington, KY 40506-0046, USA

Abstract

Condition number of a matrix is an important measure in numerical analysis and linear algebra. The general approach to obtaining it is through direct computation or estimation. The time and memory cost of such approaches are very high, especially for large size matrices. We propose a totally different approach to estimating the condition number of a sparse matrix. That is, after computing the features of a matrix, we use support vector regression (SVR) to predict its condition number. We also use feature selection strategies to further reduce the response time and improve accuracy. We bring forth a feature selection criterion which combines the weights from SVR with the weights from comparison of matrices with their preconditioned counterparts. Our experiments show that the response time of the prediction method is on average 15 times faster than the direct computation approaches, which makes it suitable for online condition number query. The accuracy of our prediction method is not as precise as the general direct computation methods. However, many people only care about whether a matrix is well-conditioned or ill-conditioned or the order of the condition number, not the exact value of the condition number. For such users, a rough prediction with quick response time probably is a better choice than a precise value after waiting for hours or days.


Key words:support vector machine, feature selection, preconditioning

Mathematics Subject Classification:


Download the compressed postscript file xu4.ps.gz, or the PDF file xu4.pdf.
Technical Report 420-04, Department of Computer Science, University of Kentucky, Lexington, KY, 2004.

The research work of S. Xu was supported in part by the U.S. National Science Foundation under grant ACR-0234270.

The research work of J. Zhang was supported in part by NSF under grants CCR-0092532 and ACR-0202934, by DOE under grant DE-FG02-02ER45961, and by the University of Kentucky Research Committee.