An online condition number query system

ABSTRACT

Condition number of a matrix is an important measure in numerical analysis and linear algebra. It is a measure of stability or sensitivity of a matrix to numerical operations. However, the direct computation of the condition number of a matrix is very expensive in terms of CPU and memory cost, and becomes prohibitive for large size matrices. We propose to use data mining techniques to estimate the condition number of a given sparse matrix. In particular, we will use Support Vector Machine (SVM) to predict the condition numbers. That is, after computing the sparsity pattern features of a matrix, we use support vector regression (SVR) to predict its condition number. This Online Condition Number Query System (OCNQS) allows the users to submit their matrices and to obtain predicted condition numbers for their matrices. The accuracy of our prediction methods may not be as precise as the direct computation methods, but it is much faster. Our online system accepts matrices in Harwell-Boeing (HB) format and in standard MATLAB format. The users can use our system to estimate the condition number of their matrices through LAPACK software as well.

REFERENCES

• 1: Z. Bai , James Demmel , A. McKenney, On computing condition numbers for the nonsymmetric eigenproblem, ACM Transactions on Mathematical Software (TOMS), v.19 n.2, p.202-223, June 1993 [doi>10.1145/152613.152617]
• 2: Kristin P. Bennett , Colin Campbell, Support vector machines: hype or hallelujah?, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.1-13, Dec. 2000 [doi>10.1145/380995.380999]
• 3: Christian H. Bischof, Incremental condition estimation, SIAM Journal on Matrix Analysis and Applications, v.11 n.2, p.312-322, Apr. 1990 [doi>10.1137/0611021]
• 4: C. H. Bischof, P. T. P. Tang. Generalizing incremental condition estimation. J. Numer. Linear Alg. Appl., 1:149--164 (1992).
• 5: G. H. Golub and C. F. Van Loan Matrix Computation. John Hopkins Univ. Press, Baltimore, 3rd Ed., 1996.
• 6: Nicholas J. Higham, FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Transactions on Mathematical Software (TOMS), v.14 n.4, p.381-396, Dec. 1988 [doi>10.1145/50063.214386]
• 7: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 8: Junshui Ma , James Theiler , Simon Perkins, Accurate on-line support vector regression, Neural Computation, v.15 n.11, p.2683-2703, November 2003 [doi>10.1162/089976603322385117]
• 9: http://math.nist.gov/MatrixMarket/
• 10: A. J. Smola. Regression Estimation with Support Vector Learning Machines. Master's Thesis. Technische Universität München, 1996.
• 11: A. J. Smola, B. Schölkopf. A tutorial on support vector regression. NeuroCOLT Technical Report Series, NC2-TR-1998-030, 1998.
• 12: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 13: V. N. Vapnik, S. Golowich, A. Smola. Support vector method for function approximation, regression estimation, and signal processing. Advances in Neural Information Processing System 9. MIT Press, Cambridge, 1997.
• 14: S. Xu, J. Zhang. A new data mining approach to predicting matrix condition numbers. Communications in Information and Systems, 4:325--340 (2004).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms

Keywords:
ACM proceedings, condition number, data mining, features of matrices