Machine-implemented process for insuring the numerical stability of gaussian elimination

Claim 2

The machine method of solving a system of linear equations by the matrix technique of Gaussian elimination comprising the steps of: performing said elimination utilizing partial pivoting; monitoring the growth of the matrix for each elimination; and completing said elimination by complete pivoting when said growth exceeds a preselected threshold.

Claim 5

The method of claim 2 wherein said method of determining said growth comprises causing said computer to compute the value of g(0)+ (n-1)h(k 1) where n is the size of said matrix, g(0) is the magnitude of the largest element initially present in said matrix, h(k 1) is the largest superdiagonal element of said matrix at the (k- 1)st step, and k is a variable running from zero to n- 1.

Claim 6

The method of claim 3 wherein said predetermined threshold comprises 8ng(0) where n is the size of said matrix and g(0) is the magnitude of the largest element initially present in said matrix.

Claim 7

The machine-implemented process of performing Gaussian elimination upon an n X n matrix using the machine-iMplemented process of partial pivoting until numerical instability develops, at which time the machine-implemented process of complete pivoting is used, wherein the improvement comprises: computing the value of V g(0)+(n- 1)h(k 1) at the end of each step of said machine-implemented process of partial pivoting, where n is the size of said matrix, g(0) is the magnitude of the largest element initially present in said matrix, h(K 1) is the largest superdiagonal element of said matrix at the (k-1)st step, and k is a variable running from zero to n- 1; comparing said computer value of V with Phi 8ng(0); and continuing said Gaussian elimination by using said process of partial pivoting if V> Phi and by using said process of complete pivoting if V Phi .

Claim 8

The machine-implemented process of performing Gaussian elimination upon an n X n matrix using the machine-iMplemented process of partial pivoting until numerical instability develops, at which time the machine-implemented process of complete pivoting is used, wherein the improvement comprises: computing the value of V g(0)+(n- 1)h(k 1) at the end of each step of said machine-implemented process of partial pivoting, where n is the size of said matrix, g(0) is the magnitude of the largest element initially present in said matrix, h(K 1) is the largest superdiagonal element of said matrix at the (k-1)st step, and k is a variable running from zero to n- 1; comparing said computer value of V with Phi 8ng(0); and continuing said Gaussian elimination by using said process of partial pivoting if V> Phi and by using said process of complete pivoting if V Phi .

Claim 9

A machine-implemented process of performing Gaussian elimination upon an n X n matrix comprising the steps of: programming a digital computer to allow it to perform Gaussian elimination by the method of partial pivoting; programming a digital computer to allow it to perform Gaussian elimination by the method of complete pivoting; programming a digital computer to begin said machine-implemented process of Gaussian elimination by performing said method of partial pivoting upon said n X n matrix; programming a digital computer to compute the value of V g(0)+(n- 1)h(k 1) at the end of each step of said process of partial pivoting where n is the size of said matrix, g(0) is the magnitude of the largest element initially present in said matrix, h(k 1) is the largest superdiagonal element of said matrix at the (k- 1)st step, and k is a variable running from zero to n-1; programming a digital computer to compare said computer value of V with Phi 8ng(0); and programming a digital computer to continue said Gaussian elimination by using said process of partial pivoting if V> Phi and by using said process of complete pivoting if V Phi .

Claim 10

A machine-implemented process of performing Gaussian elimination upon an n X n matrix comprising the steps of: programming a digital computer to allow it to perform Gaussian elimination by the method of partial pivoting; programming a digital computer to allow it to perform Gaussian elimination by the method of complete pivoting; programming a digital computer to begin said machine-implemented process of Gaussian elimination by performing said method of partial pivoting upon said n X n matrix; programming a digital computer to compute the value of V g(0)+(n- 1)h(k 1) at the end of each step of said process of partial pivoting where n is the size of said matrix, g(0) is the magnitude of the largest element initially present in said matrix, h(k 1) is the largest superdiagonal element of said matrix at the (k- 1)st step, and k is a variable running from zero to n-1; programming a digital computer to compare said computer value of V with Phi 8ng(0); and programming a digital computer to continue said Gaussian elimination by using said process of partial pivoting if V> Phi and by using said process of complete pivoting if V Phi .

Claim 11

The machine method of performing the process of Gaussian elimination upon an n X n matrix comprising the steps of: performing said Gaussian elimination process by the method of partial pivoting; determining the value of the growth of said matrix after each step of said partial pivoting process; comparing said value of growth to a predetermined threshold; and continuing said Gaussian elimination process by the method of partial pivoting if said value of growth exceeds said predetermined threshold and continuing said Gaussian elimination process by the method of complete pivoting if said value of growth does not exceed said predetermined threshold.

Claim 12

The machine method of performing the process of Gaussian elimination upon an n X n matrix comprising the steps of: performing said Gaussian elimination process by the method of partial pivoting; determining the value of the growth of said matrix after each step of said partial pivoting process; comparing said value of growth to a predetermined threshold; and continuing said Gaussian elimination process by the method of partial pivoting if said value of growth exceeds said predetermined threshold and continuing said Gaussian elimination process by the method of complete pivoting if said value of growth does not exceed said predetermined threshold.

Claim 13

The method of claim 7 wherein said step of determining said value of growth comprises: computing the value of g(0)+(n- 1)h(k 1) where n is the size of said matrix, g(0) is the magnitude of the largest element initially present in said matrix, h(k 1) is the largest superdiagonal element of said matrix at the (k- 1)st step, and k is a variable running from zero to n- 1.

Claim 14

The method of claim 8 wherein said predetermined threshold comprises 8ng(0) where n is the size of said matrix and g(0) is the magnitude of the largest element initially present in said matrix.

Claim 15

The machine method of performing the process of Gaussian elimination upon an n X n matrix comprising the steps of: performing Gaussian elimination by the method of partial pivoting: computing the value of g(0)+(n-1)h(k 1) at the end of each step of said method and said partial pivoting where n is the size of said matrix, g(0) is the magnitude of the largest element initially present in said matrix, h(k 1) is the largest superdiagonal element of said matrix at the (k- 1)st step, and k is a variable running from zero to n- 1; computing said computer value to the threshold value Sng(0); and continuing the Gaussian elimination process by using the process of partial pivoting if said computed value is greater than said threshold value and by using the process of complete pivoting if said computed value is less than or equal to said threshold value.

Claim 16

The machine method of performing the process of Gaussian elimination upon an n X n matrix comprising the steps of: performing Gaussian elimination by the method of partial pivoting: computing the value of g(0)+(n-1)h(k 1) at the end of each step of said method and said partial pivoting where n is the size of said matrix, g(0) is the magnitude of the largest element initially present in said matrix, h(k 1) is the largest superdiagonal element of said matrix at the (k- 1)st step, and k is a variable running from zero to n- 1; computing said computer value to the threshold value Sng(0); and continuing the Gaussian elimination process by using the process of partial pivoting if said computed value is greater than said threshold value and by using the process of complete pivoting if said computed value is less than or equal to said threshold value.