Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-02-08
2004-02-17
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S446000
Reexamination Certificate
active
06694343
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to the field of solving a system of linear equations. More specifically, the present invention is related to a computer-based method and a system for solving a large sparse triangular system of linear equations.
2. Discussion of Prior Art
Most natural phenomenon are modeled or simulated using a system of linear equations. Solving linear equations can be computationally intensive depending on the dimensions of the matrices involved.
FIG. 1
illustrates a general method of solving a system of linear equations and is given by:
Ax=b
(1)
Matrix
106
(of dimension n×n) represents the array or matrix representative of vector A; matrix
108
represents the array or matrix representative of vector x (of dimension
1
×n); and array or matrix
110
represents the array or matrix representative of vector b (of dimension
1
×n). Solving the system of linear equations of (1) in terms of x as given below:
x=A
−1
b=Wb
(2)
where
W=A
−1
(3)
Equation (2) provides for a solution to the system of linear equations given by
100
. Thus, the system of linear equations, in matrix form, given by
100
can be rewritten, as in
102
, in terms of the matrix or array representative of x, wherein the matrix given by
112
is the inverse of A, denoted A
−1
. The inverse of matrix A or A
−1
112
can further be presented and replaced by another matrix W
114
as in (3). The computation of x as described in
104
represents a solution to the system of linear equations given by (1) and as the dimension n of the matrices involved (
108
,
114
, and
110
) increases, so does the computational overhead of a processor trying to perform that operation.
Sparse matrices (i.e., very few non-zero elements) arise more frequently than dense matrices (i.e., very few zero elements). An example of a general structure of a sparse 4×4 square matrix is given below:
S
=
⌊
s
11
0
0
s
14
0
0
0
0
0
0
0
s
34
0
0
0
0
⌋
(
4
)
wherein the elements s
11
, s
14
, and s
34
are the only non-zero elements in (4). The diagonal of a square matrix (n×n) divides it into two halves and helps define two kinds of sparse matrices: upper-triangular or lower triangular. If the block below the diagonal consists of zeros, the matrix is said to be upper triangular. For example, the matrix shown below is upper triangular:
U
=
⌊
0
s
12
0
s
14
0
0
0
0
0
0
0
s
34
0
0
0
0
⌋
(
5
)
In contrast to (5), if the block above the diagonal consists of zeros, then the matrix is said to be lower-triangular. An example of a lower triangular matrix is shown below:
L
=
⌊
0
0
0
0
0
0
0
0
0
s
32
0
0
s
41
0
0
0
⌋
(
6
)
Matrices that are representative of a system of linear equations that simulate real life phenomenon are usually either lower (5) or upper (6) triangular and the traditional methods of solving such equations create undue computational burden on the processor. Standard methods of solving each systems may take too much time since they do not take advantage of the presence of many zero entries in a sparse matrix. Thus, they handle each entry of the sparse matrix in sequence, and generate the entries of the solution matrix, x in the case of (2), one at a time, even though many or most of them may be equal to zero. Therefore, there is a need for a system which overcomes the shortcomings of prior methods (that perform more than necessary computations) and utilizes only the non-zero components of a matrix to solve large sparse triangular linear equations and generate explicitly only the non-zero entries of the solution.
Whatever the precise merits, features and advantages of prior methods, none of them achieve or fulfills the purposes of the present invention. The current invention provides for a system that takes advantage of sparse structure of matrices (upper or lower triangular) and maintains an ordered data structure and a pair of ordered vectors that contains only the non-zero indices, their respective values, and pointers to these values. Thus the invention teaches how to solve the system more efficiently without generating zero entries of the solution explicitly. These and other objects are achieved by the detailed description that follows.
SUMMARY OF THE INVENTION
The present invention provides for a computer-based system and a method for solving a large sparse triangular system of linear equations. The invention utilizes only the non-zero components of a matrix to solve large sparse triangular linear equations and generates explicitly only the non-zero entries of the solution.
The computer-based method and system comprises three data structures: partially ordered data structure (or simply ordered data structure), contiguous list v, and vector p. A list of the row indices of the known non-zero values of x which require farther processing is stored in the ordered data structure. Actual non-zero values of x are stored in the contiguous list v and the corresponding pointers to the location of these values are stored in the vector p. The present invention manipulates these three matrices to find a solution to an upper or lower sparse triangular system of linear equations. In addition, the present invention also takes into account the case wherein a matrix becomes dense (or increases in density) by the presence of many active rows. A partitioning method is described via which the dense matrix problem is solved.
REFERENCES:
patent: 4787057 (1988-11-01), Hammond
patent: 5200915 (1993-04-01), Hayami et al.
patent: 5301342 (1994-04-01), Scott
patent: 5905666 (1999-05-01), Hoffman et al.
patent: 5983230 (1999-11-01), Gilbert et al.
patent: 6446105 (2002-09-01), Washio et al.
patent: 6470368 (2002-10-01), Garg et al.
patent: 6601080 (2003-07-01), Garg
Forrest John Joseph
Megiddo Nimrod
Tomlin John Anthony
Lacasse Randy W.
Lacasse & Associates LLC
Mai Tan V.
McSwain Marc D.
LandOfFree
Method for solving a large sparse triangular system of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for solving a large sparse triangular system of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for solving a large sparse triangular system of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3306875