Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-10-19
2004-11-30
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S520000
Reexamination Certificate
active
06826585
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to simultaneous-linear-equations solving method and apparatus for calculating numerical solutions of simultaneous linear equations. In particular, it relates to a technology that is effective when applied to a simultaneous-linear-equations solving apparatus for calculating the numerical solutions in a manner of being independent of the type (i.e., the non-zero structure) of the coefficient matrix of the simultaneous linear equations.
From conventionally, as the solving methods of solving the simultaneous linear equations the coefficient matrix of which is a dense matrix, there have existed many methods such as the Gauss method and the Crout transformation method. These methods are described in, for example, Gene H. Golub and Charles F. Van Loan, “Matrix Computations”, published by Johns Hopkins University Press, 3rd edition, 1996, pp. 94-104. In the case where the coefficient matrix has been already found to be a sparse matrix, starting with the Skyline method, there exist many solving methods as data storing methods where attention is focused on the structure of the non-zero elements of the coefficient matrix and as the solving methods of solving the simultaneous linear equations the coefficient matrix of which is the sparse matrix and which are suitable for the above-described data storing methods. The methods of solving the simultaneous linear equations the coefficient matrix of which is the sparse matrix are disclosed in, for example, “Matrix Computation Software-WS, Super Computer, and Parallel Computer”, edited/written by Tutomu Oguni, Maruzen Co., Ltd., pp. 229-231. In order to reduce the resource amount and the wasteful calculation of the zero elements needed for the data storage, it is important to select a most-suitable optimum solving method in correspondence with the structure of the non-zero elements of the coefficient matrix. This selection of the solving method necessitates the empirical and professional knowledge.
In the conventional numerical solving methods for the simultaneous linear equations, in the case of solving the simultaneous linear equations the coefficient matrix of which is the sparse matrix, the selection of the optimum solving method has necessitated the empirical and professional knowledge. As a result, a user who has no empirical and professional knowledge has found it difficult to solve the simultaneous linear equations the coefficient matrix of which is the sparse matrix.
SUMMARY OF THE INVENTION
Also, in the conventional numerical solving methods for the simultaneous linear equations, in the case where the coefficient matrix of the simultaneous linear equations to be solved is the sparse matrix, the use of the dense matrix-suitable solving methods has caused so much waste to be produced. This is especially apparent when compared with the case of using the sparse matrix-suitable solving methods in both the resource amount and the calculation amount needed for the data storage. In recent years, in a mass-storage-memory mounting apparatus the representative of which is a distributed-memory-type parallel computer or the like, the above-described waste of storing the zero elements has been becoming a less serious problem. However, there still remains the problem of the increase in the calculation amount, which occurs in the case where the dense matrix-suitable solving methods are used for solving the simultaneous linear equations the coefficient matrix of which is the sparse matrix.
It is an object of the present invention to provide a technology that makes the following possible: To solve the above-described problem, to implement an enhancement in the operability of an information processing apparatus for calculating numerical solutions of simultaneous linear equations, and to reduce the calculation amount needed for determining the solutions.
In the present invention, in the simultaneous-linear-equations solving apparatus for calculating the numerical solutions of the simultaneous linear equations the coefficient matrix of which is the sparse matrix, too, all the elements of the sparse matrix including the zero elements are stored into an array in much the same way as the case of the dense matrix. After that, a decomposition processing and a forward/backward substitution processing are executed concerning within the range of the non-zero elements thereof, thereby determining the solutions.
In the present invention, all the elements of the coefficient matrix elements of the sparse matrix including the zero elements, and all the elements of the right-side vector elements are stored into an array in much the same way as the case of the dense matrix.
Next, the values stored into the above-described array are examined, thereby creating a non-zero-structure-specifying index table for indicating the row number of a terminal-end non-zero element in each column and the column number of a terminal-end non-zero element in each row within the above-described array.
Moreover, of the coefficient matrix elements within the above-described array, the decomposition processing is executed concerning within the range of the non-zero elements indicated by the above-described created non-zero-structure-specifying index table. In addition, the forward/backward substitution processing is executed toward the coefficient matrix elements subjected to the above-described decomposition processing and the right-side vector elements stored into the above-described array, thereby determining the solutions.
As described earlier, according to the present invention, the waste of storing the zero elements is tolerated, and the same data storing methods as those for the dense matrix are employed for whatever coefficient matrix in a manner of being independent of the structure of the non-zero elements of the coefficient matrix, thereby implementing the enhancement in the operability. Namely, there is no necessity to store, into the memory, programs for causing the computer to execute the various types of solving methods for solving the simultaneous linear equations the coefficient matrix of which is the sparse matrix. Also, there is no necessity for a user to select one solving method from among the various types of solving methods. Furthermore, the calculations are executed concerning only the elements existing within the range indicated by the above-described created non-zero-structure-specifying index table. This allows the simultaneous linear equations to be solved in such a manner that the calculation amount therefor has been reduced.
As described so far, according to the simultaneous-linear-equations solving apparatus of the present invention, all the elements of the sparse matrix including the zero elements are stored into the array in much the same way as the case of the dense matrix. After that, using the above-described index table, the decomposition processing and the forward/backward substitution processing are executed concerning within the range of the non-zero elements thereof, thereby determining the solutions. This method makes it possible to implement the enhancement in the operability of the information processing apparatus for calculating the numerical solutions of the simultaneous linear equations, and to reduce the calculation amount needed for determining the solutions.
REFERENCES:
patent: 5301342 (1994-04-01), Scott
patent: 5392429 (1995-02-01), Agrawal et al.
patent: 5490278 (1996-02-01), Mochizuki
patent: 5604911 (1997-02-01), Ushiro
patent: 5717621 (1998-02-01), Gupta et al.
patent: 5887186 (1999-03-01), Nakanishi
patent: 5905666 (1999-05-01), Hoffman et al.
patent: 6694343 (2004-02-01), Forrest et al.
Gene H. Golub and Charles F. Van Loan,Matrix Computations, 3d ed., Johns Hopkins University Press (1996), pp. 94-104.
Tutomu Oguni,Matrix Computation Software—WS, Super Computer and Parallel Computer,Maruzen Co., Ltd. (1991), pp. 229-231. [No English translation available.]
Kawamura Hiroki
Mitsunaga Saori
Tanaka Shin-ichi
Hitachi Software Engineering Co. Ltd.
Mai Tan V.
LandOfFree
Method and apparatus for solving simultaneous linear equations 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 and apparatus for solving simultaneous linear equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for solving simultaneous linear equations will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3287531