A fundamental problem in the computer solution of a sparse, N by N, positive definite system of equations $Ax = b$ is, given the structure of A, to determine the structure of its Cholesky factor L, where $A = LL^T $. This problem arises because it is often desirable to set up a data structure for L before the numerical computation is performed, and in order to do this we must know the positions of the nonzeros of L. We describe a representation$\mathcal {R}_L $ for L which typically requires far fewer data items than the number of nonzeros in L, and an algorithm is then described which generates $\mathcal {R}_L $. The time and space complexity of the algorithm is shown to be $O(|A|,|\mathcal {R}_L |)$, and can never be worse than $O(|L|)$. Here $|\mathcal {R|}_L |$ denotes the number of items in the data structure for L, and $|A|$ (and $|L|$ denote the number of nonzeros in A and L respectively. For a certain class of problems, we show that the execution time of the algorithm is $O(N)$, even though $|L|$ is $O(N\log N)$. We also provide some numerical results showing that the algorithm can be implemented so that the program performance reflects its theoretically predicted behavior.

This paper describes a very fast implementation of the m~n~mum degree algorithm, which is an effective heuristm scheme for fmding low-fill ordermgs for sparse positive definite matrices.This implementation has two important features: first, in terms of speed, it is competitive with other unplementations known to the authors, and, second, its storage requirements are independent of the amount of fill suffered by the matrix during its symbolic factorization.Some numerical experiments which compare the performance of this new scheme to some existing minimum degree programs are provided.

Umversity of

The need to find nodes with large eccentricity arises in many heuristic algorithms for ordering sparse matrix equations.A computer program is presented here for finding such nodes, based on an algorithm due to Gibbs, Poole, and Stockmeyer.Several changes have been made to their original method, and experiments suggest that these changes improve its reliability and execution time.

article A Comparison of Algorithms for Solving Symmetric Indefinite Systems of Linear Equations Share on Authors: Victor Barwell Chemical Research, Ontario Hydro, Toronto, Ont., Canada Chemical Research, Ontario Hydro, Toronto, Ont., CanadaView Profile , Alan George Department of Computer Science, University of Waterloo, Waterloo, Ont., Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ont., Canada N2L 3G1View Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 2Issue 3Sept. 1976 pp 242–251https://doi.org/10.1145/355694.355697Online:01 September 1976Publication History 20citation733DownloadsMetricsTotal Citations20Total Downloads733Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access