Performance Analysis

Since invention of frontal method, many codes have been written on this approach. Almost all codes are written in Fortran⁵.They are usually written as subroutines. So one can use these subroutines as part of his own program. Some codes written for unifrontal and multifrontal algorithms are listed in Table 1. Some of them are commercial software. Subroutines in Table 1 are from Harwell Subroutine Library.

Table 1: Some Unifrontal/multifrontal Codes

code	description
MC43	Preorders elements for frontal solvers
MA27	Sparse symmetric linear equation solver.
	Multifrontal algorithm. Minumum degree ordering.
MA37	Sparse symmetric linear equation solver (symmetric or nearly so)
	Multifrontal algorithm. Minumum degree ordering.
MA38	Sparse unsymmetric linear equation solver.
	Combined unifrontal/multifrontal algorithm.
	Approximate minumum degree ordering.
MA41	Sparse unsymmetric linear equation solver.
	Multifrontal algorithm. Designed for symmetric or nearly so.
	Approximate minumum degree ordering.
MA42	Sparse symmetric linear equation solver.
	(Uni)frontal algorithm.
MA46	Sparse unsymmetric linear equation solver.
	Multifrontal algorithm. Minumum degree ordering.
MA62	Sparse symmetric positive-definite linear solver.
	(Uni)frontal algorithm.

Performance of some codes based on unifrontal,multifrontal and conbined unifrontal/multifrontal approaches are compared on a single processor CRAY YMP. Some codes are designed for symmetric matrices whereas some others based on unsymmetric-pattern. To obtain performance datas, codes are run on some test matrices. Descriptions of codes are as follows

MUPS

 [6] It was designed for parallel multifrontal schemes. Performs a minumum degree ordering and symbolic factorization on the nonzero pattern of ${\mathbf A} + {\mathbf A^T}$,and constructs an assembly tree for the numerical factorization phase. All pivots must pass the threshold partial pivoting test but test is by columns not rows. Since all other codes performs this test by rows, for the comparison MUPS factorize $\mathbf{A^T}$ then use the factors in $\mathbf{A^T}$ to solve $\mathbf{Ax=b}$. MUPS always attemps to preserve symmetry.

MA48

 [8] General sparse unsymmetric linear equation solver. It uses Markowits criteria.

GPLU

 [5] It is developed by Gilbert and Peierls. It has no pre-ordering phase. Threshold partial pivoting is used. It does not have an option to preserve symmetry.

UMFPACK V1.0

⁶ [11] It can preserve symmetry.

SSGETRF

 [9] It is a classical multifrontal method in Cray Research, Inc., library installed on CRAY YMP. It uses Liu's multiple minumum degree pivoting test. It always preserves symmetry.

Table 2: Test Matrices

name	n	$\vert A\vert$	sym.	discipline	comments
bcsstk08	1074	12960	1.000	structural eng.	TV studio, irregular
bcsstk28	4410	219024	1.000		solid element model
plat1919	1919	32399	1.000	oceanography	Atlantic and Indian oceans
orsirr_ 1	1030	6858	1.000	petroleum eng.	21x21x5 irregular grid
sherman4	1104	3786	1.000		16x23x3 grid,fully implicit
lns_3937	3937	25407	0.850	fluid flow	linearized Navier-Stokes
shyy41	4720	20042	0.723		viscous fully-coupled Navier-Stokes
mcfe	765	24382	0.699	astrophysics	radiative transfer
mahindas	1258	7682	0.017	economics	Victoria, Australia
radfr1	1048	13299	0.054	chemical eng.	non-reactive separation
lhr01	1477	18592	0.007		light hydrocarbon recovery
lhr71	70304	1528092	0.002		light hydrocarbon recovery

Test matrices are listed in Table  2. The table lists the name, order, number of entries, symmetry, the discipline where it comes from and additional comments. Symmetry of a matrix is defined as the number of mathced off- diagonal entries over the total number of off-diagonal entries. An entry, $a_{ij} (j\ne i)$, is matched if $a_{ji}$ is also an entry. If this number is 1 then the matrix is symmetric. All matrices are available via ftp.cis.ufl.edu:pub/umfpack/matrices.

Table 3: Run time in seconds on a single processor of a CRAY YMP C-98-512Mw-8.

matrix	discipline	UMFPACK	MA48	MUPS	SSGETRF	GPLU
bcsstk08	structural eng.	0.342	0.416	0.708	0.588	21.044
bcsstk28		1.564	6.771	1.204	2.896	312.059
plat1919	oceanography	0.595	1.816	0.415	failed	21.716
orsirr_ 1	petroleum eng.	0.196	0.317	0.209	0.193	5.297
sherman4		0.099	0.125	0.134	0.133	0.903
lns_3937	fluid flow	1.869	5.437	1.899	1.746	38.213
shyy41		0.472	1.145	0.681	0.509	7.407
mcfe	astrophysics	0.343	0.426	0.324	0.399	7.065
mahindas	economics	0.164	0.085	0.663	0.892	1.793
radfr1	chemical eng.	0.206	0.254	0.214	0.316	3.480
lhr01		0.430	0.426	1.026	1.170	6.381
lhr71		52.480	164.034	failed	174.761	failed

The best runtimes of the codes for the test matrices are shown in Table 3. The time is in seconds, and includes both the analysis and factorizaton times. The fastest time for each matrix is shown in bold. Table 4 lists the memory used for the runs whose times are listed in Table 3. The smallest memory usage is shown in bold.

Table 4: Memory usage in megawords on a single processor of a CRAY YMP.

matrix	discipline	UMFPACK	MA48	MUPS	SSGETRF	GPLU
bcsstk08	structural eng.	0.229	0.295	0.187	0.170	0.524
bcsstk28		2.162	3.043	1.674	1.236	2.023
plat1919	oceanography	0.669	0.890	0.363	failed	0.371
orsirr_ 1	petroleum eng.	0.180	0.230	0.152	0.108	0.203
sherman4		0.078	0.085	0.068	0.060	0.063
lns_3937	fluid flow	1.044	1.908	1.121	1.193	0.738
shyy41		0.374	0.618	0.486	0.349	0.294
mcfe	astrophysics	0.267	0.430	0.310	0.202	0.219
mahindas	economics	0.085	0.074	0.208	0.143	0.073
radfr1	chemical eng.	0.136	0.142	0.108	0.096	0.107
lhr01		0.240	0.238	0.435	0.287	0.141
lhr71		23.145	34.403	failed	35.268	failed