Browse Prior Art Database

APL Algorithm to Solve Sparse Systems of Equations

IP.com Disclosure Number: IPCOM000080576D
Original Publication Date: 1974-Jan-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 45K

Publishing Venue

IBM

Related People

Brennan, PA: AUTHOR [+3]

Abstract

An essential tool for the design (and thus fabrication) of computer circuit hardware is a means for analyzing circuits and circuit devices. The modified nodal approach (MNA), shown in the IBM Technical Disclosure Bulletin, Vol. 16, No. 7, December 1973, pp. 2408-2412, entitled "Modified Nodal Approach (MNA) to Network Analysis and Design", by, P. A. Brennan, C. W. Ho, and A. Ruehli, to network analysis satisfies this need. In applying the MNA to problems, a unique sparse system of equations results. When programmed in APL, techniques which are fundamentally different from those used in such languages as FORTRAN or PL/1 are required to solve this system efficiently. A method is proposed which is essentially the following:

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

APL Algorithm to Solve Sparse Systems of Equations

An essential tool for the design (and thus fabrication) of computer circuit hardware is a means for analyzing circuits and circuit devices. The modified nodal approach (MNA), shown in the IBM Technical Disclosure Bulletin, Vol. 16, No. 7, December 1973, pp. 2408-2412, entitled "Modified Nodal Approach (MNA) to Network Analysis and Design", by, P. A. Brennan, C. W. Ho, and A. Ruehli, to network analysis satisfies this need. In applying the MNA to problems, a unique sparse system of equations results. When programmed in APL, techniques which are fundamentally different from those used in such languages as FORTRAN or PL/1 are required to solve this system efficiently. A method is proposed which is essentially the following:

Starting from the MNA, equations are generated and placed in sparse matrix form. The matrix is then rearranged so that the solution can be accomplished in as few steps as possible. This includes proper choice of pivots (as discussed in the above-mentioned reference) and forming a vector of matrix pointers for the rearranged matrix, which is also stored as a vector.

The techniques involved in solving the equations utilize a mix of a sparse Gaussian elimination method plus built in APL functions. Everything is tailored to vector/matrix operations that are very efficient in APL. The APL function domino particularly is used in the algorithm. It is an equation solver that operates on any matrix, sparse or full. Depending upon the particular computer being used, domino will provide faster solutions than any sparse matrix algorithm up to a certain size matrix. Beyond this size, sparse matrix methods will be faster. The size of the matrix is also dependent upon the amount of storage available, since domino can require large storage because it treats all matrices as full.

Storage places an upper limit on that part of the matrix which domino can process, and the crossover point between it and sparse matrix methods determines whether the actual matrix size is less than this upper bound. Thus, for matrices up to a certain size, domino could be used exclusively. Beyond this size, it is combined with sparse matrix methods to give the fastest running time. These matrix sizes can be experimentally obtained for each particular computer on which the program is run. Gaussian Elimination Scheme.

The figure is a schematic representation of how the different portions of the matrix are stored. The two regions of 0 entries due to row a...