In this section, we report our experiments on the accuracy and response time of the condition number prediction methods. We use SVMlight for SVM regression. There are 277 matrices from Matrix Market tested in the experiments. We use altogether 60 matrix features. First, We test how accurate the predicted condition numbers are, compared with the directly computed condition numbers. The figure below illustrates the percentage of all matrices for which the relative differences between the computed values and the predicted values of the condition number are within 10, 10^2, 10^3, 10^4, respectively.

Given a matrix, the time used to obtain the condition number is referred to as the response time. The response time for the LAPACK method is the time to compute the condition number using LAPACK routines.The response time for the prediction method includes the time to compute matrix features and the time for prediction. Here we also compare the response time for prediction using the whole matrix features and using half of the features. Table 1 shows the average response time for the 277 matrices used in our tests. The prediction methods are 15 times faster than using LAPACK on average.

6 seconds is also an acceptable time for an online query systems. Prediction with feature selection is only slightly faster than without any feature selection. Using half of the features does not mean reducing the time cost by half.

TABLE 1
Average response time (in seconds).
LAPACK
Prediction (all)
Prediction (FS)
99.23
6.56
6.32

The prediction method is especially advantageous in response time for large size matrices. For example, in Table 2 the average LAPACK response time for the 78 matrices with size larger than 2000 is around 6 minutes, while using the prediction methods, the response time is only about 20 seconds.

TABLE 2
Average response time for larger size matrices (in seconds).
Size
Num of Mat.
LAPACK
Prediction(all)
Prediction(FS)
>= 1000
119
227.22
15.17
14.62
>= 2000
78
340.74
22.81
21.99

Table 3 gives some examples of how the prediction methods exceed the LAPACK method in response time. For instance, LAPACK uses about two and a half hours to compute the condition number of the matrix ADD20, the prediction methods only need less than one second.

TABLE 3
Matrix name
Size
nnz
LAPACK
Prediction(all)
Prediction(FS)
ADD20
2395
13151
8206.7
0.94
0.81
CRY10000
10000
49699
2262.4
23.41
24.01
LNS_3937
3937
25407
2977.0
1.38
1.33
PSMIGR_1
3140
543160
2129.8
15.82
3.31

Copyright 2001 - 2006 HiPSCCS lab