Two data mining algorithms for predicting the condition number of sparse matrices

Dianwei Han

Email: dianweih@csr.uky.edu
Postal address: University of Kentucky, Computer Science, 773 Anderson Hall, Lexington, Ky. 40506-0046

We present experimental results of comparing the Modified K-Nearest Neighbor (MkNN) algorithm with Support Vector Machine (SVM) in the prediction of condition numbers of sparse matrices. Condition number of a matrix is an important measure in numerical analysis and linear algebra. 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 use data mining techniques to estimate the condition number of a given sparse matrix. In our previous work, we used Support Vector Machine (SVM) to predict the condition numbers. While SVM is considered a state-of-the-art classification/regression algorithm, kNN is usually used for collaborative filtering tasks.

Since prediction can also be interpreted as a classsification/regression task, virtually any supervised learning algorithm (such as kNN) can also be applied.

Experiments are performed on a publicly available dataset. We conclude that Modified kNN (MkNN) performs much better than SVM on this particular dataset.