4.2. Computational Time

The execution time (in elapsed CPU seconds) for the three ordering schemes discussed in Section 3 have been obtained on a Sun Microsystems SPARCstation 20 (50 MHz). The RCM reordering was implemented using the Fortran code from Sparspak [CGLN84]. The Fiedler reordering was produced using the Lanczos (with selective re-orthogonalization) software from Chaco 2.0 [HL94], and the reorderings using Correspondence Analysis were derived using the block Lanczos routine ( bls2) from SVDPACKC [B+93]. Table 12 lists the actual reordering times obtained by each method for the four hypertext matrices presented in Section 3.2.

Consistent with the analytic complexity discussed in Section 3.3, the execution time required by RCM is indeed low. In fact, the spectral-based reordering schemes require at least two orders of magnitude (i.e., 100 times) more execution time than RCM for these particular hypertext matrices. The dominant computational cost of the spectral-based methods involves multiplications by the sparse matrix A (and ) as they naturally arise in iterative methods such as Lanczos for computing singular triplets. The total number of multiplications of the form y=Ax or for both spectral methods is provided in Table 12. Clearly, the cost of computing the largest singular triplet (first pair of principal axes) with CANC(1) is far less than that of computing the second-largest singular triplet by CACS(2) or the second-smallest eigenvectors of the (m+n) by (m+n) Laplacian matrix L in Equation (4) by the Fiedler approach. However, as illustrated in Figures 3 and 4, the savings in sparse matrix multiplications (a factor ranging from 3 to 5 from the results in Table 12) for CANC(1) may be offset by an inferior bandwidth and envelope reduction for hypertext clustering (e.g., see Figure 4(d)). Correspondence Analysis with distances (i.e., CACS(2)) would appear to be more competitive with respect to bandwidth (and envelope) reduction at an increased computational cost.