US 7,065,545 B2Granted

Computer methods of vector operation for reducing computation time

OwnerRaul Gerardo Quintero-de-la-Garzainventor

Life of this patent

Estimating the term…

Abstract

A computer method of vector operations for calculating the inverse of a general square matrix and for solving linear equations systems. The invention comprises a new method of factorization and executing multiply-add operations useful for effecting dot-product operations of one-dimensional vectors. This new method reduces the computation time over computers programmed to use prior art methods.

Claims6

Dependent claims

A computer method of solving a system of linear equations of the general form [A][X]=[B], by means of a digital computer, comprising the steps of:

(a) representing the linear equations system in said digital computer in the form of an extended matrix [A|B], formed by N×N+1 elements aij, which are indexed as an arrangement of N rows and N+1 columns;
(b) selecting a first row of elements of said matrix having a first element different from zero;
(c) normalizing the values of the elements of said first row by dividing all elements of said first row by the value of the first non-zero element;
(d) setting the initial value of a first index “e”, associated with the sequential order of selection of the rows, to 2;
(e) selecting a second row of said matrix;
(f) calculating the values of the elements of a transformation vector [K] according to the formula:
K
n
=
{
1
≤
n
<
e
;
-
a
en
-
∑
i
=
1
n
-
1
⁢
(
a
in
*
K
i
)
n
=
e
;
1
}
where “n” is a second index associated with the sequential order of the n-th element of the vector [K] being calculated and “e” is said first index associated with the sequential index of the row being transformed;
(g) transforming the values of each of the elements of the selected second row by performing the dot product of said vector [K] and a vector formed by those “e” elements of each column of the extended matrix [A|B] corresponding to the rows that have been transformed prior to the selection of said second row;
(h) determining whether element aee of matrix [A|B] is zero;
(i) if element aee is zero, then determining whether index “e” is equal to the number of columns “n”;
If aee is not zero, then modifying the value of said index “e” so that another row of said extended matrix is selected;
(j) selecting a third row of said extended matrix and repeating steps (f) to (h) until a row is found with a nonzero element aee;
(k) normalizing row “e” by dividing all elements of row “e” by the value of said element aee;
(l) determining from the value of said first index “e” whether all rows of said matrix have been transformed;
if all rows have not been transformed, then modifying the value of said index “e” so that another row of said extended matrix is selected;
(m) repeating steps (e) to (j) until all rows of said matrix have been transformed;
thereby obtaining an upper diagonal matrix [U] with all elements uij located in the main diagonal having a value of 1, and all elements below the main diagonal having a value of zero;
and
(n) sequentially back-substituting the value of the nth element of vector [x] according to the following formula:
x
i
=
(
b
i
-
∑
j
=
i
+
1
n
⁢
u
ij
⁢
x
j
)
u
ii
for i=n−1, n−2, . . . 1;
whereby the calculated vector [x] is the solution vector of the original system of linear equations.

76 more elements

A computer method of solving a system of linear equations by means of a digital computer, comprising the steps of:

(a) representing the linear equations system in said digital computer in the form of an extended matrix [A|B], formed by N×N+1 elements aij, which are indexed as an arrangement of N rows and N+1 columns;
(b) selecting a first row of elements of said matrix having a first element different from zero;
(c) normalizing the values of the elements of said first row by dividing all elements of said first row by the value of the first non-zero element;
(d) setting the initial value of a first index “e”, associated with the sequential order of selection of the rows, to 2;
(e) selecting a second row of said matrix;
(f) calculating the values of the elements of a transformation vector [K] according to the formula:
K
n
=
{
1
≤
n
<
e
;
-
a
en
-
∑
i
=
1
n
-
1
⁢
(
a
i
⁢
⁢
n
*
K
i
)
n
=
e
;
1
}
where “n” is a second index associated with the sequential order of the n-th element of the vector [K] being calculated and “e” is said first index associated with the sequential index of the row being transformed;
(g) calculating the value of the element aee of said matrix by performing the dot product of said vector [K] and a vector formed by the “e” elements of each column of the extended matrix [A|B] corresponding to the rows that have been transformed prior to the selection of said second row;
(h) determining whether the element aee of matrix [A|B] has a non-zero value;
(i) if element aee is zero, then determining, from the value of said first index “e”, whether all columns of the matrix have been transformed;
If all columns have not been transformed, then selecting another row of said extended matrix and repeating steps (f) to (h) until a row is found with a non-zero valued element aee;
(j) recalculating the values of the elements of a transformation vector [K] according to the formula:
K
n
=
K
n
a
ee
′
1
≤
n
≤
e
where “n” is an index associated with the n-th element of vector [K] being calculated and “e” is an index associated with the sequential index of the row being transformed;
(k) transforming the values of each of the elements of said second row by performing the dot product of said vector [K] and a vector formed by the first “e” elements of each column of the extended matrix [A|B];
(l) determining from the value of said first index “e” whether all rows of said matrix have been transformed;
if all rows have not been transformed, then modifying the value of said index “e” so that another row of said extended matrix is selected;
(m) repeating steps (f) to (j) until all rows of said matrix have been transformed;
thereby obtaining a transformed upper diagonal matrix [U] with all elements uij located in the main diagonal having a value of 1, and all elements below the main diagonal having a value of zero;
and
(n) sequentially back-substituting the value of the nth element of vector [x] according to the following formula:
x
i
=
(
b
i
-
∑
j
=
i
+
1
n
⁢
u
ij
⁢
x
j
)
u
ii
for i=n−1, n−2, . . . 1;
whereby the calculated vector [x] is the solution vector of the original system of linear equations.

93 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/140,788Filed 7 May 2002
Published: US 2003/0212723 A113 Nov 2003
Granted: 20 Jun 2006
Term ends: Not estimatedThe source records don’t support an estimate.

Classification3 codes

G06F 17/12
For solving equations , e.g. nonlinear equations, general mathematical optimization problems: simultaneous equations , e.g. systems of linear…
G06F 17/16
Complex mathematical operations: matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
G06F
Computing and data processing

Family

US 2003/0212723 A1Pre-grant publication · published 13 Nov 2003
US 7,065,545 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

patentgrep

Loading patent…

Abstract

A computer method of solving a system of linear equations of the general form [A][X]=[B], by means of a digital computer, comprising the steps of:

(a) representing the linear equations system in said digital computer in the form of an extended matrix [A|B], formed by N×N+1 elements aij, which are indexed as an arrangement of N rows and N+1 columns;
(b) selecting a first row of elements of said matrix having a first element different from zero;
(c) normalizing the values of the elements of said first row by dividing all elements of said first row by the value of the first non-zero element;
(d) setting the initial value of a first index “e”, associated with the sequential order of selection of the rows, to 2;
(e) selecting a second row of said matrix;
(f) calculating the values of the elements of a transformation vector [K] according to the formula:
K
n
=
{
1
≤
n
<
e
;
-
a
en
-
∑
i
=
1
n
-
1
⁢
(
a
in
*
K
i
)
n
=
e
;
1
}
where “n” is a second index associated with the sequential order of the n-th element of the vector [K] being calculated and “e” is said first index associated with the sequential index of the row being transformed;
(g) transforming the values of each of the elements of the selected second row by performing the dot product of said vector [K] and a vector formed by those “e” elements of each column of the extended matrix [A|B] corresponding to the rows that have been transformed prior to the selection of said second row;
(h) determining whether element aee of matrix [A|B] is zero;
(i) if element aee is zero, then determining whether index “e” is equal to the number of columns “n”;
If aee is not zero, then modifying the value of said index “e” so that another row of said extended matrix is selected;
(j) selecting a third row of said extended matrix and repeating steps (f) to (h) until a row is found with a nonzero element aee;
(k) normalizing row “e” by dividing all elements of row “e” by the value of said element aee;
(l) determining from the value of said first index “e” whether all rows of said matrix have been transformed;
if all rows have not been transformed, then modifying the value of said index “e” so that another row of said extended matrix is selected;
(m) repeating steps (e) to (j) until all rows of said matrix have been transformed;
thereby obtaining an upper diagonal matrix [U] with all elements uij located in the main diagonal having a value of 1, and all elements below the main diagonal having a value of zero;
and
(n) sequentially back-substituting the value of the nth element of vector [x] according to the following formula:
x
i
=
(
b
i
-
∑
j
=
i
+
1
n
⁢
u
ij
⁢
x
j
)
u
ii
for i=n−1, n−2, . . . 1;
whereby the calculated vector [x] is the solution vector of the original system of linear equations.

76 more elements

Facts

Application

10/140,788Filed 7 May 2002

Published

US 2003/0212723 A113 Nov 2003

Granted

20 Jun 2006

Term ends

Not estimatedThe source records don’t support an estimate.

Classification3 codes

G06F 17/12
For solving equations , e.g. nonlinear equations, general mathematical optimization problems: simultaneous equations , e.g. systems of linear…
G06F 17/16
Complex mathematical operations: matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
G06F
Computing and data processing