Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1999-05-10
2003-10-21
Broda, Samuel (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C708S007000, C708S446000, C712S007000, C712S035000
Reexamination Certificate
active
06636828
ABSTRACT:
This application is based on Japanese Patent Application No. 10-127738 filed May 11, 1998, which application is incorporated herein by reference in its entirety.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a symbolic calculation system and a symbolic calculation method, both for performing a symbolic calculation to solve simultaneous linear equations, and also relates to a parallel circuit simulation system which effects a circuit simulation by solving the simultaneous linear equations.
2. Description of the Related Art
Generally speaking, a process for solving simultaneous linear equations involves a symbolic calculation process and a numerical calculation process. An example of the symbolic calculation process, involved in the process for solving simultaneous linear equations, is described in the third section “Sparse Matrix Methods” of “Fundamentals of Computer-Aided Circuit Simulation” (written by William J. McCalla and published in 1988).
FIG. 11
is a flowchart showing the symbolic calculation process involved in the aforementioned conventional process for solving simultaneous linear equations.
Firstly, a single entry set E is prepared, and information (entries) specifying the positions of nonzero elements contained in a coefficient matrix is sequentially added to the entry set E. Further, an array R(k) representing the number of entries contained in the k
th
row and an array C(k) representing the number of entries contained in the k
th
column are also prepared and updated at the time of adding the entries (a step S
410
).
Next, the use of a variable i, representing a count which is incremented each time the symbolic calculation process is repeated, is declared, and the initialization procedure of substituting the value “1” for “i” is conducted (a step S
420
). Following this, the value of “W” which results in the minimum value of R(w)×C(w) is determined (a step S
430
). In obtaining the values of R(w) and C(w) in the step S
430
, the entries specifying the elements contained in those parts of the matrix which correspond to eliminated variables and equations and the entries specifying diagonal elements are not counted.
After the value of “W” has been determined, the i
th
and w
th
rows of the entry set E are replaced with each other, as well as the i
th
and w
th
columns thereof (a step S
440
). Then, fill-ins which take place at the time of eliminating the i
th
variable are computed, and entries specifying the fill-ins are added to the entry set E (a step S
450
).
When the step S
450
is finished, the variable i is incremented by 1 (a step S
460
). Next, it is determined whether the value of the variable i exceeds “m−1” (a step S
470
). When it is determined in the step S
470
that the value of the variable i does not exceed m−1, a return is made to the step S
430
. By repeating the steps S
430
to S
470
, the optimum pivot order and the positions in which the fill-ins take place can be determined.
On the other hand, when it is determined in the step S
470
that the value of the variable i exceeds m−1, the coefficient matrix is compressed using the entry set E to which the entries have been added in the steps S
410
and S
450
. Matrix data, obtained as a result of the compression, is stored in a storage area of a storage device or the like (a step S
480
), and the process shown in the flowchart is terminated. When the process of
FIG. 11
is terminated, then the numerical calculation process is conducted.
However, the conventional process for solving the simultaneous linear equations has the following drawbacks:
Firstly, in the case where a parallel computer of distributed memory type executes the symbolic calculation process, a single node has to carry out the steps of the symbolic calculation process one after another. Under this condition, the capacity of a local memory included in the node restricts the size of the coefficient matrix which can be handled.
Secondly, in the case where the coefficient matrix which is a square matrix has a size of m×m (which indicates the number of rows and columns included in the coefficient matrix), the time required for completing the symbolic calculation process increases substantially in proportion to m
1
to m
3
. Hence, as the coefficient matrix size becomes large and as the number of entries which are added to the entry set becomes excessive, the symbolic calculation process cannot be finished within a practical length of time.
The above-described drawbacks occur also in the case of performing a circuit simulation which entails the process for solving simultaneous linear equations.
SUMMARY OF THE INVENTION
The present invention has been made in consideration of the above drawbacks, and it is accordingly an object of the present invention to provide a symbolic calculation system and a symbolic calculation method, which can handle a large-scale matrix and whose calculation time is short.
It is another object of the present invention to provide a parallel circuit simulation system which can perform a large-scale circuit simulation at high speed.
According to the first aspect of the present invention having the above-described objects, there is provided a symbolic calculation system which performs a symbolic calculation to solve simultaneous linear equations, comprising:
a plurality of nodes each having an element processor and local memory including a program area which stores a predetermined program to be executed by the corresponding element processor and a work area used by the element processor, and an interconnection network which interconnects the plurality of nodes, wherein the element processors of the plurality of nodes are capable of cooperating with each other,
the symbolic calculation system comprising a first computer which is connected to the interconnection network, and which divides a matrix, representing the simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix,
wherein each of the plurality of nodes corresponds to each row set divided by the first computer, and each of the element processor executes the predetermined program stored in the program area thereby each of the plurality of nodes:
adds entries specifying nonzero elements contained in the row sets associated with the plurality of nodes to a plurality of entry sets which are in one-to-one correspondence with the plurality of row sets;
sequentially attains a first variable which specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix, by cooperating with other nodes;
replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, by cooperating with other nodes;
replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix, by cooperating with other nodes;
obtains fill-ins belonging to the associated row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to the matrix including the rows and/or columns replaced with each other, and further adding entries specifying the obtained fill-ins to the plurality of entry sets to the entry sets.
According to this symbolic calculation systems, the plurality of nodes carry out the addition of the entries in a parallel fashion. This enables the symbolic calculation in solving the simultaneous linear equations to be performed at high speed.
In the case of realizing the aforementioned symbolic calculation systems with parallel computers of distributed memory type, the data amount corresponding to the product of the reciprocal of the number of parts in which the matrix is divided and the amount of data when a single node performs the addition of the entries to an entry set will be
Broda Samuel
NEC Electronics Corp.
Phan Thai
Scully Scott Murphy & Presser
LandOfFree
Symbolic calculation system, symbolic calculation method and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Symbolic calculation system, symbolic calculation method and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symbolic calculation system, symbolic calculation method and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3134123