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.

Michael W. Berry (berry@cs.utk.edu)

Mon Jan 29 14:30:24 EST 1996