Browse Prior Art Database

Gauss Elimination Method Using Boolean Strings

IP.com Disclosure Number: IPCOM000078263D
Original Publication Date: 1972-Dec-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 3 page(s) / 26K

Publishing Venue

IBM

Related People

Buturla, EM: AUTHOR

Abstract

This technique provides a sparse matrix algorithm that may be used to solve large sets of linear equations. The coefficient matrix must be positive, definite, symmetric and sparse, such as the type of matrix derived from energy principles. Nonzero terms of the matrix along with compressed Boolean Strings are used in a modified Gauss-elimination scheme. Computer main memory requirements and solution time are reduced relative to the conventional banded Gauss-elimination algorithm.

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 57% of the total text.

Page 1 of 3

Gauss Elimination Method Using Boolean Strings

This technique provides a sparse matrix algorithm that may be used to solve large sets of linear equations. The coefficient matrix must be positive, definite, symmetric and sparse, such as the type of matrix derived from energy principles. Nonzero terms of the matrix along with compressed Boolean Strings are used in a modified Gauss-elimination scheme. Computer main memory requirements and solution time are reduced relative to the conventional banded Gauss- elimination algorithm.

We start with the general matrix equation

A . x = b (1) where

A = coefficient matrix

b = constant vector

x = unknown vector

Equation (1) is then partitioned as shown:

(Image Omitted)

From Eq. (6), we observe that one of the unknown, x(1) had been reduced out of, or eliminated from, the analysis. The matrix A(22) - A(21) A(11)/-1/ A(12) is now an (n-1) by (n-1) matrix; we partition the new matrix as in Eq. (1) and reduce out the second unknown. We continually partition and reduce until the vector x(2) is reduced to a single term, x(n). At that time, all of the matrices in Eq. (7) will be single terms and we can easily solve for the last unknown, x(n). Substituting x(n) into Eq.
(5) will yield x(n-1) and continued back substitution will yield the entire unknown vector.

An efficient method for representing the reduced matrix A(22) consists of storing and manipulating only nonzero terms of the matrix, and having some type of code indicating column position of the nonzero terms for each row. Storing the column location of the nonzero terms along with each of the terms, makes the total memory requirement two times the number of nonzero terms. However, a much more efficient code involves the use of Boolean strings.

In reducing the A(22) matrix, we are subtracting the matrix A(21) . A(11)/-1/ . A(12) and, therefore, the terms reducing matrix A(22) are the Boolean string for the...