Accession Number : ADA328678

Title :   Two Improved Algorithms for Envelope and Wavefront Reduction.

Descriptive Note : Contractor rept.,

Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s) : Kumfert, Gary ; Pothen, Alex

PDF Url : ADA328678

Report Date : JUL 1997

Pagination or Media Count : 36

Abstract : Two algorithms for reordering sparse, symmetric matrices or undirected graphs to reduce envelope and wavefront are considered. The first is a combinatorial algorithm introduced by Sloan and further developed by Duff, Reid, and Scott; we describe enhancements to the Sloan algorithm that improve its quality and reduce its run time. Our test problems fall into two classes with differing asymptotic behavior of their envelope parameters as a function of the weights in the Sloan algorithm. We describe an efficient O(n log n + m) time implementation of the Sloan algorithm, where n is the number of rows (vertices), and rn is the number of nonzeros (edges). On a collection of test problems, the improved Sloan algorithm required, on the average, only twice the time required by the simpler Reverse Cuthill-McKee algorithm while improving the mean square wavefront by a factor of three. The second algorithm is a hybrid that combines a spectral algorithm for envelope and wavefront reduction with a refinement step that uses a modified Sloan algorithm. The hybrid algorithm reduces the envelope size and mean square wavefront obtained from the Sloan algorithm at the cost of greater running times. We illustrate how these reductions translate into tangible benefits for frontal Cholesky factorization and incomplete factorization preconditioning.

Descriptors :   *ALGORITHMS, *GRAPHS, *DATA REDUCTION, *SPARSE MATRIX, *WAVEFRONTS, TEST AND EVALUATION, SIZES(DIMENSIONS), PARAMETERS, REDUCTION, COSTS, SPECTRA, SYMMETRY, ASYMPTOTIC SERIES, HYBRID SYSTEMS, COMBINATORIAL ANALYSIS, MEAN, COLLECTION, ENVELOPE(SPACE).

Subject Categories : Numerical Mathematics
      Optics

Distribution Statement : APPROVED FOR PUBLIC RELEASE