Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-06-26
2004-09-28
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C703S002000, C712S010000
Reexamination Certificate
active
06799194
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an iteration method used to solve simultaneous linear equations, and more specifically to a processing apparatus for performing a preconditioning process in the iteration method.
2. Description of the Related Art
In analyzing a physical phenomenon, it is often necessary to solve simultaneous linear equations containing a large matrix as a coefficient matrix as follows.
Ax=b (1)
where A indicates a coefficient matrix of n×n, x indicates an n-dimensional variable vector, and b indicates an n-dimensional constant vector. It is not rare that the value of n is approximately 10
6
.
The above described large simultaneous linear equations are used in various scientific and engineering computation for weather forecasting, designing an atomic furnace, analyzing a semiconductor circuit, analyzing a fluid in aeronautics, analyzing a structure, etc. Therefore, it is one of the important objects in the scientific and engineering computation to efficiently and quickly solve large simultaneous linear equations.
One of the methods for solving an equation (1) using a computer is a direct method based on the Gaussian elimination method in which A is LU-factorized. However, when A is a large sparse matrix, there can be only a few non-zero elements in each row, and it is wasteful in computation cost and storage area. Therefore, in such cases, an iteration method is often used to obtain an approximate solution by repeatedly obtaining simple matrix-vector products.
A preconditioning process is used as a method for accelerating the convergence of the iteration method on a sparse matrix. In this process, the equation (1) is transformed as follows using an appropriate preconditioner matrix M
−1
.
M
−1
Ax=M
−1
b (2)
By applying the iteration method to the equation (2) above, an approximate solution of the equation (1) can be obtained. At this time, M corresponds to the block incomplete factorization (BIF) of A, and M
−1
indicates an inverse matrix of M. Thus, an algebraic multilevel iteration method is known as a method of performing such a preconditioning process through the block incomplete factorization of A.
However, the preconditioning process in the above mentioned conventional algebraic multilevel iteration method has the following problems.
Normally, the preconditioning process in the algebraic multilevel iteration method can be applied to a problem in which a coefficient matrix A is an M-matrix, and has the function of accelerating the convergence. That A is an M-matrix refers to that A=(a
ij
) is a regular matrix, and satisfies the following two conditions.
(1) a
ij
≦0 (i‡j) (non-diagonal elements of A are 0 or negative)
(2) A
−1
≧0 (all elements of inverse matrix A
−1
of A are not negative)
However, when A is not an M-matrix, the preconditioning process in the algebraic multilevel iteration method does not effectively work, and the computation does not converge.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a processing apparatus for performing a preconditioning process capable of accelerating the convergence of computation in the iteration method used on simultaneous linear equations in which a coefficient matrix is not an M-matrix.
The processing apparatus according to the present invention comprises a coefficient storage unit, a determination unit, a set storage unit, an inverse matrix unit, a coefficient matrix unit, a factorization unit, and a computation unit and performs a preconditioning process for an iteration method used to solve simultaneous linear equations through performing multilevel block incomplete factorization.
The coefficient storage unit stores a coefficient matrix at a certain level in the block incomplete factorization. The determination unit determines a set of variable numbers of variables to be removed so that a block matrix comprising elements, which have the variable numbers of the variables to be removed as row numbers and column numbers, of the coefficient matrix stored in the coefficient storage unit can be diagonal dominant.
The set storage unit stores information about the determined set of variable numbers. The inverse matrix unit obtains an approximate inverse matrix of the block matrix according to the information stored in the set storage unit.
The coefficient matrix unit obtains a coefficient matrix at a coarse level from a block matrix comprising elements, which have variable numbers of remaining variables as row numbers and column numbers, of the coefficient matrix stored in the coefficient storage unit.
The factorization unit stores the coefficient matrix at the coarse level in the coefficient storage unit to perform subsequent block incomplete factorization. The computation unit computes a matrix-vector product in the iteration method using the approximate inverse matrix.
REFERENCES:
patent: 5604911 (1997-02-01), Ushiro
patent: 6144932 (2000-11-01), Hachiya
patent: 6360190 (2002-03-01), Kumashiro
patent: 2002/0091909 (2002-07-01), Nakanishi
Grosz Lutz
Nakanishi Makoto
Fujitsu Limited
Malzahn David H.
Staas & Halsey , LLP
LandOfFree
Processing apparatus for performing preconditioning process... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processing apparatus for performing preconditioning process..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing apparatus for performing preconditioning process... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3229792