JP2006048637A - Simultaneous linear equation calculation program, simultaneous linear equation calculator, and simultaneous linear equation solving method - Google Patents

Abstract

The present invention makes it possible to solve a large-size simultaneous linear equation having a general multi-diagonal matrix as a coefficient matrix at a high speed only by an analyst following a certain procedure.
A simultaneous linear equation having a block tridiagonal matrix as a coefficient matrix is input (S100), and a block tridiagonal matrix expression generated based on the block tridiagonal matrix is input into four rows. Using the block square matrix of 4 columns as a unit, the division / compression process is recursively repeated up to the upper limit of the number of divisions determined from the size of this block square matrix (S150 to S200). And the solution of simultaneous linear equations is calculated | required by tracing these processes reversely (S210-S240). At this time, an inverse matrix of the block square matrix is calculated using a predetermined algebraic relational expression (S140).
[Selection] Figure 2

Description

The present invention relates to a calculation program for simultaneous linear equations, a calculation apparatus for simultaneous linear equations, and a method for solving simultaneous linear equations, and more particularly to a method for directly calculating simultaneous linear equations having a general multi-diagonal matrix as a coefficient matrix using a computer. The present invention relates to a simultaneous linear equation calculation program, a simultaneous linear equation calculator, and a simultaneous linear equation solving method.

Examining the dynamics of natural phenomena through analysis of mathematical models is important for building highly controllable engineering systems. Normally, the dynamics of natural phenomena are described by mathematical models such as differential equations and difference equations, but these mathematical models cannot generally be solved analytically except in very typical cases.

Therefore, in the analysis of the mathematical model, it is essential to obtain a numerical solution using a calculation device (computer). At this time, in the calculation apparatus, a discretized equation obtained by discretizing the differential equation using a difference method, a finite element method, a boundary element method, a finite volume method, or the like is numerically processed. When the mathematical model is given as a difference equation from the beginning, the difference equation becomes a direct calculation target of the computer.

The discretization equation usually uses an unknown vector in which the unknown to be obtained (that is, a discretized variable) is expressed in vector and a known vector corresponding to the known numerical value, and “coefficient matrix × unknown vector = known. It is expressed in matrix form as simultaneous linear equations in the form of “number vector”. For the sake of simplicity, hereinafter, the coefficient matrix when the simultaneous linear equations are expressed in matrix will be simply referred to as the coefficient matrix of the simultaneous linear equations.

There is a direct method as one of methods for obtaining a numerical solution of a discretized equation using a computer. The direct method, as described above, considers the discretized equation as a simultaneous linear equation, and calculates the unknown vector by calculating this simultaneous linear equation using an algebraic algorithm such as the LU decomposition method or the Gaussian elimination method. This is a direct method. If this method is used, calculation errors other than rounding errors are theoretically eliminated, so it is possible to obtain a highly accurate numerical solution. However, when the size of the coefficient matrix is large (that is, the elements of the coefficient matrix). When the number is very large), a large amount of memory is required for calculation using the algebraic algorithm described above, and a very long calculation time is required.

In order to solve such a problem, Patent Document 1 discloses a large size 3
A calculation program based on a solution process for numerically calculating simultaneous linear equations having a multi-diagonal matrix as a coefficient matrix at high speed is disclosed. Non-Patent Documents 1 and 2 disclose details of mathematical aspects of this solution process.

The solution process described in Patent Document 1 is summarized as follows (see FIGS. 3 and 7).

Step 1: A simultaneous linear equation obtained by discretizing a differential equation, an initial condition, and a boundary condition input by an analyst is expressed in a matrix format of “coefficient matrix × unknown number vector = known number vector”. Patent Document 1 exemplifies a case of a scalar tridiagonal matrix as the coefficient matrix. A scalar tridiagonal matrix is a tridiagonal matrix in which all components are scalars.

Step 2: The scalar tridiagonal matrix that is the coefficient matrix is divided into s sub-matrices according to the division number s (s is an integer equal to or greater than 2) input by the analyst. Accordingly, the unknown vector is also divided into s groups. As a result, the above simultaneous linear equations are
Each of these sub-matrices is divided into a group of s simultaneous linear equations (this will be referred to as a group of s simultaneous linear equations). Here, since the coefficient matrix is a scalar tridiagonal matrix, the unknowns located at both ends of the s−1 dividing line are two adjacent simultaneous linear equation groups located on both sides of the dividing line. (This unknown is called shared unknown).

Step 3: Extract the unknowns located at the extreme ends of the unknown vector (referred to as boundary unknowns) and the shared unknown and extract those unknowns (referred to as compression unknowns). (The simultaneous linear equation thus formed will be referred to as a compression simultaneous linear equation).

  Step 4: The inverse matrix of the coefficient matrix of the above-mentioned compressed simultaneous linear equations is obtained using a normal calculation method. By this operation, all the values of the compression unknown are obtained.

Step 5: The compression unknown value thus obtained is substituted into the s simultaneous linear equations. Then, the above s simultaneous linear equations are completely linearly separated (ie, reduced to completely independent s simultaneous equations having no shared unknowns), so that these linearly separated s All the remaining unknowns can be determined by obtaining an inverse matrix of each coefficient matrix of a group of simultaneous linear equations using a normal calculation method.
The advantage of this solution is that a simultaneous linear equation having a tridiagonal matrix to be analyzed as a coefficient matrix can be systematically divided into a plurality of small simultaneous linear equations. As a result, even if the coefficient matrix of the simultaneous linear equations to be analyzed is a huge size, each simultaneous linear equation is systematically divided into multiple simultaneous linear equations with a small matrix as the coefficient matrix. Can be performed in parallel. As a result, by using a plurality of central processing units (CPUs), it is possible to perform calculation of individual simultaneous linear equations in parallel. There is an advantage that the entire calculation time can be greatly shortened as compared with the case of using an existing algebraic algorithm in the direct method such as the elimination method.

Furthermore, when the size of the coefficient matrix of the simultaneous linear equations to be numerically calculated is very large, the above steps 2 to 4 are repeated recursively according to the number of divisions input by the analyst. Is also disclosed. As a result, the sizes of the sub-matrices can be gradually reduced, and the inverse matrix of these sub-matrices can be calculated in a short time.

As described above, the solving process of simultaneous linear equations described in Patent Document 1 uses a direct method, so that the calculation accuracy is high and the solving method itself is skillful, and an existing direct calculation algorithm is used. Although it is very excellent in that the calculation time can be greatly shortened as compared with the case where it has been, there are two problems shown below as the possibility of further development.

<Problem 1> In Patent Document 1, when dividing a coefficient matrix of simultaneous linear equations into sub-matrices in a computing device, the optimum number of coefficient matrix divisions (size of division) and the number of divisions are clearly specified. Not done.

In this regard, FIG. 8A of Patent Document 1 shows that the calculation time tends to decrease as the number of divisions increases. In this case, it can be seen that the calculation time is the shortest when the number of divisions is 250 (that is, the size of the divided small matrix is 400 × 400). Further, FIG. 8B shows that the calculation time decreases rapidly until the number of divisions is 50, and the calculation time tends to decrease gradually when the number of divisions is more than that. In addition, FIG.
12 (B) shows that the calculation time tends to be shortened as the number of divisions increases.

  However, when an analyst uses a computing device, one of the important things is that the number of conditions to be input is small and the degree of freedom of selection of values to be substituted for each condition is small. When the analyst uses the calculation apparatus described in Patent Document 1, the analyst must input the size of the coefficient matrix of the simultaneous linear equations and the number of divisions. At this time, even if the analyst has information on the above-described tendency, in practice, there is too much room for selection with respect to the size of division and the number of divisions. This becomes more noticeable as the coefficient matrix size increases. Furthermore, the input target input by the analyst usually differs depending on the level of the analyst or the type of mathematical model to be analyzed, but Patent Document 1 does not consider that.

For this reason, the calculation device described in Patent Document 1 has a problem that it is difficult for general analysts including professional analysts skilled in numerical analysis.

<Problem 2> Patent Document 1 exemplifies a case where the coefficient matrix of the simultaneous linear equations to be analyzed is a scalar tridiagonal matrix, but in general, the coefficient matrix is a scalar tridiagonal matrix. Not necessarily.

A typical example in which the coefficient matrix of the simultaneous linear equations is a scalar tridiagonal matrix is when the system to be analyzed has only local interaction between elements.

However, as the scale of the system to be analyzed increases, not only the local interaction between adjacent elements but also the influence of non-local (long-distance) interaction between distant elements can be ignored. Along with this, a time lag will inevitably occur in information transmission between elements. Such a large-scale system is generally modeled by a functional partial differential equation. The functional partial differential equation includes an integral term representing the effect of nonlocal interaction (or a higher-order differential term of the third or higher order) in addition to the differential term up to twice. In a discretized equation obtained by discretizing such a functional partial differential equation, a summation term obtained by discretizing the integral term (or the discretized term of the higher order differential) appears. The coefficient matrix of the simultaneous linear equations expressing such discretized equations in a matrix is not a scalar tridiagonal matrix, and even in a simple case, a band matrix (that is, a scalar multiple pair or more). Square matrix).

Therefore, the computing device described in Patent Document 1 still has a problem that it is difficult to handle when numerically analyzing the dynamics of a large-scale system in which non-local interaction exists between elements.
JP 2002-312341 A “Direct high-speed solution of simultaneous linear equations by discretization of differential equations (vibration analysis of N-layer structure using split layering method)”, Kenzo Koriyasu, Noriyuki Hiramoto, Mitsuji Tanimoto, Minetada Kosano; Collection (C) Vol.68, No.672, pp.2217-2224 (2002) “A New Efficient Solver for Huge Linear Algebraic Equations Derived from Fluid Dynamics”, T. Hiramoto, M. Osano, and K. Oshima, Computer Fluid Dynamics JOURNAL, vol. 11, No. 3, pp. 346-357 (2002)

The present invention has been made in order to solve the above two problems at the same time. The object of the present invention is to convert a general multi-diagonal matrix into a coefficient matrix just by following a certain procedure. It is intended to provide a simultaneous linear equation calculation program, a simultaneous linear equation calculation apparatus, and a simultaneous linear equation solving method capable of solving a large-size simultaneous linear equation at high speed.

In order to achieve the above object, the present invention according to claim 1 is directed to a computer for solving simultaneous linear equations, and to input a block tridiagonal matrix having a square matrix as a coefficient matrix of the simultaneous linear equations. Based on the prompting coefficient matrix input means and the input of the block tridiagonal matrix,
A block tridiagonal matrix notation generating means for generating a block tridiagonal matrix notation (block tridiagonal matrix × block unknown vector = block known number vector) from the simultaneous linear equations, and the block triple pair A division number determination means for determining the number of divisions based on the size of the angle matrix, and the block tridiagonal matrix notation formula are divided into a plurality of divided block matrix notation formulas (divided block matrixes) in units of a 4 × 4 block square matrix. A block matrix notation dividing unit that divides as x divided block unknown vector = divided block known number vector) and a divided block inverse matrix that is an inverse matrix of the plurality of divided block matrices using a predetermined algebraic relational expression A block inverse matrix computing means, the plurality of divided block unknown vectors, the plurality of divided block known vectors, A plurality of renormalization block matrix notation generating means for generating a plurality of renormalization block matrix notations (divided block unknown vector = divided block inverse matrix × division block renormalization vector) from the plurality of division block inverse matrices; Compressed block matrix notation generating means for generating a compressed block matrix notation (compressed block matrix × compressed block unknown vector = compressed block renormalization vector) by extracting and compressing only vector components located at the boundary portion of the matrix notation; The recursive operation control means for recursively repeating the operations from the division to the compression with respect to the compressed block matrix expression with the determined number of divisions as an upper limit, and the number of divisions by the recursive operation control means. All compressed blocks obtained by repeating to the upper limit The inverse calculation solution for obtaining the value of the compressed block unknown vector in the matrix notation formula by applying the plurality of divided block inverse matrices generated by the divided block inverse matrix generation means in the reverse order from the operation from the division to the compression. It is made to function as a means.

The present invention described in claim 2 is a computer program for simultaneous linear equations according to claim 1,
The division number determining means determines the number of divisions based on the order of each term when the size of the block tridiagonal matrix is expanded to a power-of-two series.

A third aspect of the present invention is the simultaneous linear equation calculation program according to the first or second aspect, wherein the division number determining means has a relational expression when the size of the block tridiagonal matrix is p. The number of divisions is determined as a natural number f that satisfies p = 2 ^{f + 2} .

The present invention according to claim 4 is a computing device for solving simultaneous linear equations, wherein coefficient matrix input means for prompting input of a block tridiagonal matrix having a square matrix as a coefficient matrix of the simultaneous linear equations Based on the input of the block tridiagonal matrix, a block triple that generates a block tridiagonal matrix expression (block tridiagonal matrix × block unknown vector = block known vector) from the simultaneous linear equations Diagonal matrix notation generation means, division number determination means for determining the number of divisions based on the size of the block tridiagonal matrix, and the block tridiagonal matrix notation are expressed as a 4 × 4 block square matrix. Is a block matrix notation that divides as a plurality of divided block matrix notation formulas (divided block matrix x divided block unknown vector = divided block known number vector) Dividing means, divided block inverse matrix calculating means for calculating a divided block inverse matrix that is an inverse matrix of the plurality of divided block matrices using a predetermined algebraic relational expression, the plurality of divided block unknown vectors, the plurality of divided block unknown vectors, Renormalization block matrix notation generating means for generating a plurality of renormalization block matrix expressions (division block unknown vector = division block inverse matrix × division block renormalization vector) from the division block known number vector and the plurality of division block inverse matrices. And compression to generate a compressed block matrix notation (compressed block matrix × compressed block unknown vector = compressed block renormalization vector) by extracting and compressing only the vector components located at the boundaries of the plurality of renormalization block matrix notations A block matrix notation generation means, and the determined Repetitive operation control means for recursively repeating the operations from the division to compression on the compressed block matrix notation, with the upper limit of the number of divisions, and the recursive operation control means being repeated up to the upper limit of the number of divisions. The compressed block unknown vector values in all the compressed block matrix notation expressions obtained in the above are used in the order reverse to the operation from the division to compression of the plurality of divided block inverse matrices generated by the divided block inverse matrix generation means. It is characterized by comprising reverse calculation solution means obtained by applying to the above.

The present invention according to claim 5 is a calculation method for solving simultaneous linear equations using a computer, and prompts input of a block tridiagonal matrix having a square matrix as a coefficient matrix of the simultaneous linear equations. Based on the first step and the input of the block tridiagonal matrix, a block tridiagonal matrix expression (block tridiagonal matrix × block unknown vector = block known vector) is generated from the simultaneous linear equations. A second step, a third step of determining the number of divisions from the size of the block tridiagonal matrix, and a block tridiagonal matrix notation formula, wherein a block square matrix of 4 rows and 4 columns has a plurality of units. A fourth step of dividing as a divided block matrix notation (divided block matrix × divided block unknown vector = divided block known vector), and the plurality of divided A fifth step of calculating a divided block inverse matrix which is an inverse matrix of the block matrix using a predetermined algebraic relational expression, the plurality of divided block unknown vectors, the plurality of divided block known number vectors, and the plurality of divided blocks From the block inverse matrix,
Sixth step of generating a plurality of renormalization block matrix notation formulas (divided block unknown vector = divided block inverse matrix × division block renormalization vector), and extracting only vector components located at the boundary of the plurality of renormalization block matrix notations A compressed block matrix notation (7th step of generating a compressed block matrix x compressed block unknown vector = compressed block renormalization vector) by compressing the compressed block matrix notation with the determined number of divisions as an upper limit; Compressed blocks in all the compressed block matrix notations obtained by repetitively repeating the fourth to seventh steps with respect to the eighth step and the eighth step up to the upper limit of the number of divisions The value of the unknown vector is calculated in the fifth step. The ninth step is characterized in that the ninth step is obtained by applying the generated plurality of divided block inverse matrices in the reverse order to the operation from the division to the compression.

The present invention according to claim 6 is a method for solving simultaneous linear equations according to claim 5, wherein in the third step, each size when the size of the block tridiagonal matrix is expanded to a power series of 2 is used. The number of divisions is determined based on the order of terms.

The present invention according to claim 7 is a method for solving simultaneous linear equations according to claim 5 or 6,
In the third step, when the size of the block tridiagonal matrix is p, the number of divisions is determined as a natural number f that satisfies the relational expression p = ^{2f + 2} .

According to the present invention, when the input of a block tridiagonal matrix is prompted as a coefficient matrix of simultaneous linear equations and an inverse matrix of the input block tridiagonal matrix is obtained, a 4 × 4 block square matrix is obtained. By obtaining an inverse matrix of this block square matrix as a unit of division using a predetermined algebraic relational expression stored in the main memory in advance, a huge size simultaneous linear having a general multi-diagonal matrix as a coefficient matrix It is possible to find the solution of the equation in a short time.

Further, according to the present invention, as described above, the number of divisions and the number of divisions can be uniquely determined by using a 4 × 4 block square matrix as a unit of division.

Furthermore, according to the present invention, it is possible to prompt the input of a block N (N is an integer of 4 or more) multi-diagonal matrix or a scalar q multi-diagonal matrix (q is an integer of 3 or more) as the coefficient matrix. In this case, by converting this coefficient matrix into a block tridiagonal matrix, it is possible not only to obtain the same effect as described above, but also the level of the analyst or the mathematical model to be analyzed. Since the input target according to the type can be set in multiple stages, it is possible to provide a computing device that is easier to handle for the analyst.

Furthermore, according to the present invention, a mathematical model having a complex nonlocal interaction from a mathematical model having only a normal local interaction by treating a block multi-diagonal matrix having a matrix as a unit component as a coefficient matrix. Until now, mathematical models in a wide range of engineering fields can be targeted for numerical calculations.

First, in order to facilitate understanding of the present invention, main terms used in this specification will be described.

A “scalar matrix” represents a matrix having a scalar as a unit component. For example, a scalar square matrix means a square matrix having a scalar as a unit component.

Next, the “block matrix” represents a matrix having a matrix as a unit component. For example, the block N (N is an integer of 3 or more) multi-diagonal matrix means an N-multi diagonal matrix having a square matrix as a unit component. Further, the N double diagonal component of the block N double diagonal matrix is referred to as a block N double diagonal component. In the N-fold diagonal matrix, the distance z from the diagonal line to the non-zero component farthest away from the diagonal is called the half band width, and the N-fold diagonal matrix is a symmetric matrix (ie,
If N is an odd number greater than or equal to 3, the half band width z is defined as z = (N−1) / 2. In the present invention, when the N-fold diagonal matrix is an asymmetric matrix (that is, N is an even number of 4 or more), the half-band width z is defined as z = N / 2.

When the unit component may be either a scalar or a matrix, it will be referred to as a “general matrix”. For example, a general multi-diagonal matrix may be a multi-diagonal matrix having a scalar as a unit component or a block multi-diagonal matrix having a matrix as a unit component.
In addition, when the term “matrix” is simply used, the type of unit component depends on the context.

The matrix used in this specification means a square matrix regardless of the unit component unless otherwise specified.

Next, the “block vector” represents a vector having a vector as a unit component. For example, the block unknown vector means an unknown vector having a vector as a unit component. When the unit component is a scalar, it is simply referred to as “vector”.

The “zero matrix” represents a matrix in which all components are zero. Therefore,
The “non-zero matrix” represents a matrix having at least one non-zero element among all the components.

In this embodiment, it is assumed that the block N double diagonal components of the block N double diagonal matrix are all non-zero matrices, but of course, a zero matrix may be included therein. Absent.

Also, regarding the size of the matrix, if you say "block matrix size",
It means the number of rows or columns in the unit of the square matrix that is the unit component. For example, a block matrix size value p means a block matrix of p rows and p columns with a square matrix as a unit, that is, a block matrix having p ² square matrices as unit components.

  Next, embodiments according to the present invention will be described in detail with reference to the drawings.

Depending on the type of coefficient matrix of the simultaneous linear equations to be analyzed or the level of the analyst, in particular, 3
One embodiment will be described in detail with reference to the drawings.

(First embodiment)
FIG. 1 is a conceptual diagram showing a schematic configuration of a simultaneous linear equation calculation apparatus according to the first embodiment of the present invention.

The first embodiment assumes that the coefficient matrix of the simultaneous linear equations to be analyzed is a block tridiagonal matrix.

As shown in FIG. 1, the computing device according to the first embodiment includes an input device 100 and an output device 2.
00, a central processing unit (CPU) 300, a main memory 400, and a sub memory 50
0 is connected via an external bus 600.

The input device 100 is a device for inputting simultaneous linear equations to be analyzed and various analysis conditions such as initial conditions and boundary conditions necessary for solving them. For example, a keyboard, a touch panel, a tablet, etc. Can be used.

The output device 200 is a device for displaying simultaneous linear equations and various analysis conditions input from the input device 100, and displaying analysis results. For example, the output device 200 is a CRT display, TFT display, plasma display, or the like. Various displays, various printers such as inkjet printers and laser printers can be used.

The main memory 400 is a RAM (Random Access Memory) or ROM (Read Only) that stores a calculation program of simultaneous linear equations according to the present embodiment.
Memory) or the like.

The central processing unit 300 obtains a solution of simultaneous linear equations using various analysis conditions input from the input device 100 in accordance with the above-described calculation program stored in the main memory 400, and the analysis results are displayed in a table, graph, It is a device that outputs to the output device 200 as shown in the figure.

The central processing unit 300 executes the above-described calculation program stored in the main memory 400, thereby enabling each function (each unit described in claims) of the simultaneous linear equation calculation device according to the present embodiment. Realize.

The sub memory 500 is a device for temporarily storing values such as a block matrix and a block inverse matrix obtained by the central processing unit 300 during the calculation, and a storage device such as a RAM or a hard disk can be used. It is. The sub memory 500 includes an analysis condition storage area 510, a block tridiagonal matrix notation storage area 520, and a first basic block inverse matrix storage area 54.
0 ₁ , first compressed block matrix notation storage area 550 ₁ , r th basic block inverse matrix storage area 540 _r , r th compressed block matrix notation storage area 550 _r, and f (final) basic block inverse Matrix storage area 540 _f and f-th (final) compressed block matrix notation storage area 550 _f
It is divided into areas such as Here, r is an integer that satisfies 2 ≦ r ≦ f−1.

The calculation apparatus of the present embodiment configured as described above performs numerical calculation on the simultaneous linear equations to be analyzed by the following processing procedure.

FIG. 2 is a flowchart showing a processing procedure of numerical calculation performed by the calculation apparatus of the first embodiment shown in FIG.

First, the central processing unit 300 uses the input device 100 as a coefficient matrix when a simultaneous linear equation to be analyzed is expressed as a matrix “coefficient matrix × unknown number vector = known number vector”. The analyst is prompted to input a block tridiagonal matrix of p rows and p columns having a square matrix as a unit component (step 100). Specifically, the central processing unit 300 prompts the analyst to input only the block tridiagonal component in the block tridiagonal matrix.

In step 100, the central processing unit 300 prompts the analyst to input a power-of-two value as the size p of the block tridiagonal matrix, which is a unit component of the block tridiagonal matrix. The square matrix size value z is not particularly limited except that it is a natural number.

In the present embodiment, as described above, the value p of the size of the block tridiagonal matrix.
However, it is also possible to input a general natural number other than that. This will be described later.

Further, in step 100, the central processing unit 300 corresponds to the input of the block tridiagonal matrix as the coefficient matrix described above, and p rows having an unknown vector of z rows and 1 column as a unit component as a block unknown vector. The analyst is prompted to input a block unknown vector of one column and a block known vector of p rows and one column having a unit vector of an unknown vector of z rows and one column as a block known vector.

Further, in step 100, the central processing unit 300 prompts the analyst to input various analysis conditions such as initial conditions and boundary conditions necessary for solving the simultaneous linear equations to be analyzed.

The central processing unit 300 then inputs the block tridiagonal matrix size value p, the square matrix size value z that is a unit component of the block tridiagonal matrix, the initial condition, Analysis conditions such as boundary conditions are stored in the analysis condition storage area 510 of the sub memory 500.

Next, the central processing unit 300, from the simultaneous linear equations input as described above,
Block tridiagonal matrix notation as initial matrix notation

Is generated (step 110).

here,

Is

Is a block tridiagonal matrix with p rows and p columns. Here, the block tridiagonal component of the block tridiagonal matrix (2) is a nonzero matrix of z rows and z columns input from the input device 100. The other components “O” are all zero matrices.

And

Is

Is a block unknown vector of p rows and 1 column expressed as Here, the unit component of the formula (3)

Is

Is an unknown vector of z rows and 1 column expressed as

Also,

Is

P × 1 block known vector represented as Here, the unit component of the formula (5)

Is

Is a known number vector of z rows and 1 column expressed as Note that analysis conditions such as initial conditions and boundary conditions input from the input device 100 are introduced into the known number vector (6).

Then, the central processing unit 300 stores the block tridiagonal component of the block tridiagonal matrix (2) and the block known number vector (5) in the block tridiagonal matrix notation storage area of the sub memory 500. 520 stores it.

Next, in order to obtain a block unknown vector (3) which is a solution of the simultaneous linear equations to be analyzed, a calculation algorithm described in Patent Document 1 is used.

First, the central processing unit 300 reads from the analysis condition storage area 510 of the sub memory 500,
Read the value p of the size of the block tridiagonal matrix (2), and determine the number of divisions (unary) from the read value p

A natural number f satisfying the above is obtained (step 120), and this natural number f is set as the upper limit of the number r of divisions (step 130).

The central processing unit 300 then sets the initial value of the number of divisions r to r = 1 and starts the first division process (step 140).

The central processing unit 300 converts the block tridiagonal matrix notation (1) into a first divided block matrix that is a 4 × 4 block square matrix.

Is divided into k ₁ (= p / 4 = 2 ^f ) equal parts (step 150). This process will be referred to as a first division process.

As a result, the central processing unit 300 converts the block tridiagonal matrix notation (1) into the first divided block matrix notation.

Is generated. Here, the block vector on the left side of the first divided block matrix notation (9) is referred to as a first divided block unknown vector, and the block vector on the right side is referred to as a first divided block known vector.

Next, the central processing unit 300 directly substitutes the block tridiagonal component of the first divided block matrix (8) into the first algebraic relational expression shown in Expression (11), thereby obtaining the first divided block matrix ( 8) The first divided block inverse matrix that is the inverse matrix

Is calculated (step 160).

Here, the first algebraic relational expression (11) is

And is described in advance in the calculation program of the main memory 400. here,

It was. In the formula (11), but the subscript of the formula (10) is clearly only the elements of the i = 1, i = 2, ..., subscript is changed also the elements of k ₁ I just omitted it because it has the same shape.

The central processing unit 300 then converts all matrix components of the first divided block inverse matrix (10) (generally all non-zero matrices) into the first divided block inverse matrix storage area 540 ₁ of the sub memory 500. Remember me.

Next, the central processing unit 300 reads out all the matrix elements of the first divided block inverse matrix storage area 540 ₁ of the first divided block inverse matrix of the sub-memory 500 (10), first
Using the divided block matrix notation (9),

Is generated. here,

It is.

In the first divided block known number vector on the right side of Expression (13), the vector component belonging to the boundary portion of the adjacent first divided block unknown vector

This is referred to as a first divided block renormalization vector. Further, Equation (13) will be referred to as a first renormalization block matrix notation.

Next, the central processing unit 300 uses the first renormalization block matrix notation (13) to the formula (
Only the vector component at the boundary shown in 15) is extracted and compressed (step 170). This process will be referred to as a first compression process.

here,

as well as,

It was.

Next, the central processing unit 300 calculates the equation (15)

From (15) by substituting

Is calculated. here,

It is.

Equation (19) is a simultaneous linear equation consisting of 2k ₁ vectors. This will be referred to as a first compressed block vector equation.
In this way, the central processing unit 300 performs the first compressed block vector equation (19
) To first compressed block matrix notation

Is generated (step 180). here,

Is

Is a 2k ₁ row 2k ₁ column block square matrix. This will be referred to as a first compressed block matrix.

Also,

Is

2k ₁ × ₁ block vector expressed as This will be referred to as a first compressed block unknown vector.

Also,

Is

2k ₁ × ₁ block vector expressed as This will be referred to as a first compressed block renormalization vector. Furthermore, the block known number vector of the first term on the right side of Expression (24) will be referred to as a first compressed block known number vector.

Then, the central processing unit 300 transmits the non-zero matrix component of the first compressed block matrix (22) (
However, the unit matrix I is excluded) and the first compressed block known number vector of the first compressed block renormalization vector (24) are stored in the first compressed block matrix notation storage area 55 of the sub memory 500.
0 ₁ to be stored.

The first division process and the first compression process are collectively referred to as a first connection process.

Thereafter, the central processing unit 300 recursively executes substantially the same process as the above first connection process by incrementing the value of the number of divisions r from r = 2 to f.
Repeatedly (steps 190 and 200). In order to show the characteristics in the second and subsequent connection processes, the r-th connection process will be described. Here, r is an integer that satisfies 2 ≦ r ≦ f.

The central processing unit 300 receives the (r-1) th compressed block matrix from the r-1th compressed block matrix notation storage area of the sub memory 500.

The non-zero matrix component of the r-1th compressed block matrix generated from the read non-zero matrix component

Is an r-th divided block matrix that is a 4 × 4 block square matrix

Is divided into k _r (= k _r−1 / 2 = 2 ^{f + 1−r} ) equal parts (step 150). This process will be referred to as the r-th division process.

As a result, the central processing unit 300 determines the r-th compressed block matrix notation from the r-1th compressed block matrix notation.
Partitioned block matrix notation

Is generated. Here, the block vector on the left side of the r-th divided block matrix notation (26) is referred to as the r-th divided block unknown vector, and the right-side block vector is referred to as the r-th divided block known number vector.

Next, the central processing unit 300 directly substitutes the non-zero matrix component of the r-th divided block matrix (25) into the r-th algebraic relational expression shown in Expression (28), so that the r-th divided block matrix (2
5) the r-th divided block inverse matrix that is the inverse matrix

Is calculated (step 160).

Here, the r-th algebraic relation (28) is

And is described in advance in the calculation program of the main memory 400. In the formula (28), but the subscript of the formula (27) is clearly only the elements of the i = 1, i = 2, ..., subscript is changed also the elements of k _r I just omitted it because it has the same shape.

The central processing unit 300 then stores the non-zero matrix component (except for the unit matrix I) of the r-th divided block inverse matrix (27) in the r-th divided block inverse matrix storage area 540 _r of the sub memory 500. Let

Next, the central processing unit 300 reads the non-zero matrix component of the r-th divided block inverse matrix (27) from the r-th divided block inverse matrix storage area 540 _r of the sub memory 500, and the r-th divided block matrix notation formula. Using (26)

Is generated.

The r-th divided block known vector on the right side of Expression (29) includes a vector component belonging to the boundary portion of the adjacent r-th divided block unknown vector.

Is transferred to the r-th divided block transfer vector. Equation (29) is referred to as an r-th renormalization block matrix notation.

Next, the central processing unit 300 calculates the equation (29) from the r-th renormalization block matrix notation (29).
Only the vector component at the boundary shown in 30) is extracted and compressed (step 170). This process will be referred to as the r-th compression process.

here,

as well as,

It was.

Next, the central processing unit 300 has the following expression (30).

From (30) by substituting

Is calculated.

Equation (34) is a simultaneous linear equation composed of 2k _r vectors. This will be referred to as the r-th compressed block vector equation.
In this way, the central processing unit 300 determines that the r-th compressed block vector equation (34
) To r-th compressed block matrix notation

Is generated (step 180).

here,

Is

Is a block square matrix of 2k _r rows and 2k _r columns expressed as This will be referred to as the r-th compressed block matrix.

Also,

Is

Is a 2k _r row 1 column block vector. This is referred to as an r-th compressed block unknown vector.

Also,

Is

Is a 2k _r row 1 column block vector. This will be referred to as the r-th compressed block renormalization vector. Furthermore, the block known number vector of the first term on the right side of Equation (38) will be referred to as the r-th compressed block known number vector.

The central processing unit 300 then transmits a non-zero matrix component (r) of the r-th compressed block matrix (36).
However, the unit matrix I is excluded) and the r-th compressed block known vector of the r-th compressed block renormalization vector (38) are stored in the r-th compressed block matrix expression storage area 55 of the sub memory 500.
0 is stored in the _r.

The r-th division process and the r-th compression process are collectively referred to as an r-th connection process.

In this way, the central processing unit 300 recursively repeats the r-th connection process until the value r of the number of divisions becomes f (steps 190 and 200).

  The final process (r = f) is as follows.

The central processing unit 300 reads the non-zero matrix component of the f-1 compressed block matrix from the f-1 compressed block matrix notation storage area 550 _r of the sub memory 500, and generates the first generated from the read non-zero matrix component. The f-1 (final) divided block matrix which is a 4-by-4 block square matrix of the f-1 compressed block matrix

And k _f = k _f−1 / 2 = 2 are divided into equal parts (step 150). This process will be referred to as the f-th (final) division process.

As a result, the central processing unit 300 determines that the f-th compressed block matrix notation formula
(Final) Partitioned block matrix notation

Is generated. Here, the block vector on the left side of the f-th divided block matrix notation (39) represents the f-th (final) divided block unknown vector, and the block vector on the right side represents the f-th block vector.
This will be referred to as a (final) divided block known number vector.

Next, the central processing unit 300 directly substitutes the non-zero matrix component of the f-th divided block matrix (39) into the f-th algebraic relational expression shown in Expression (42), thereby obtaining the f-th divided block matrix (3
9) The f-th (final) divided block inverse matrix that is the inverse matrix of

Is calculated (step 160).

Here, the f-th algebraic relation (42) is

And is described in advance in the calculation program of the main memory 400.

The central processing unit 300 then converts the non-zero matrix component (except the unit matrix I) of the f-th divided block inverse matrix (41) into the f-th (final) divided block inverse matrix storage area 540 of the sub memory 500. Remember to _f .

Next, the central processing unit 300 reads the non-zero matrix component of the f-th divided block inverse matrix (41) from the f-th divided block inverse matrix storage area 540 _f of the sub memory 500, and the f-th divided block matrix notation formula. (40)

Is generated.

The f-th divided block known number vector on the right side of Expression (43) is a vector component belonging to the boundary portion of the adjacent f-th divided block unknown vector.

Is transferred to the f-th (final) divided block transfer vector. Equation (43) is referred to as an f-th (final) renormalization block matrix notation.

Next, the central processing unit 300 obtains an equation (43) from the f-th renormalization block matrix notation (43).
Only the boundary portion shown in 44) is taken out and compressed (step 170). F.
This will be referred to as the (final) compression process.

here,

as well as,

It was.

Next, the central processing unit 300 has the following expression (44).

From equation (44) by substituting

Is calculated.

Expression (48) is a simultaneous linear equation composed of 2k _f-1 (= 4) vectors. This is the f (final)
This will be referred to as a compressed block vector equation.
In this way, the central processing unit 300 performs the f-th compressed block vector equation (48
) To f (final) compressed block matrix notation

Is generated (step 180). here,

Is

Is a 4 × 4 block square matrix. This will be referred to as the f (final) compressed block matrix.

Also,

Is

Is a 4 × 1 block vector. This will be referred to as the f (final) compressed block unknown vector.

Also,

Is

Is a 4 × 1 block vector. This will be referred to as the f-th (final) compressed block renormalization vector. Furthermore, the block known number vector of the first term on the right side of Equation (52) will be referred to as the f (final) compressed block known number vector.

The central processing unit 300 then calculates a non-zero matrix component of the f-th compressed block matrix (50) (
However, the first f compressed block known number vector of the unit matrix I are excluded) a renormalization first f compressed block vector (52), the f (final sub-memory 500) is stored in the connection block matrix notation equation storing region 550 _f.

The f-th division process and the f-th compression process are collectively referred to as an f (final) connection process.

Next, the central processing unit 300 obtains the block unknown vector (3) using the plurality of r-th connected block matrix notations generated in this way (steps 210 to 210).
240). Here, r is an integer that satisfies 1 ≦ r ≦ f. These steps will be referred to as back calculation solution steps.

First, the central processing unit 300 reads the non-zero matrix component of the f compressed block matrix from the f compressed block matrix notation equation storing region 550 _f of the sub-memory 500 (50), the read nonzero matrix elements formula (54 ) Is directly substituted into the f + 1 algebraic relational expression shown in FIG.
F + 1-th compressed block inverse matrix which is an inverse matrix of one compressed block matrix (50)

Is calculated (step 210).

Here, the f + 1-th algebraic relational expression is

And is described in advance in the calculation program of the main memory 400.

Next, the central processing unit 300 uses the f-th compressed block matrix notation (49),

Is generated.

Next, the central processing unit 300

From equation (55)

Is generated.

Next, the central processing unit 300 reads out the first f compressed block known number vector renormalization first f compressed block from the f compressed block matrix notation equation storing region 550 _f of the sub-memory 500 vector (52), read the f Substituting the compressed block known number vector into the equation (57), the divided unknown number vector of the block unknown number vector (3)

Is calculated (step 220).

Next, the central processing unit 300

From equation (43)

Is generated. And the value of the unknown vector that has already been obtained is shown in equation (60).

Similarly, the unknown vector (59) already obtained is substituted, and the block unknown vector (3)
The unknown vector divided into

Is calculated. This makes the unknown vector

The value of is obtained.

In this way, the central processing unit 300 repeats the above process until r = 1 in the equation (29) (steps 230 and 240), whereby all unknown vectors, that is, the block unknown vector (3), Ask for.

(Second Embodiment)
FIG. 3 is a conceptual diagram showing a schematic configuration of a simultaneous linear equation calculation apparatus according to the second embodiment of the present invention. In addition, the same code | symbol is attached | subjected to the structure same as 1st Embodiment, and repeated description is abbreviate | omitted.

The second embodiment assumes that the coefficient matrix of the simultaneous linear equations to be analyzed is a block N (N is an integer of 4 or more) multidiagonal matrix.

  In the following, N represents an integer of 4 or more.

As shown in FIG. 3, the computing device according to the second embodiment is similar to the first embodiment in the input device 100, the output device 200, the central processing unit (CPU) 300, the main memory 400, and the like. The sub memory 500 is connected via an external bus 600.

The sub memory 500 according to the present embodiment includes a block N in addition to the storage area of the first embodiment.
A multi-diagonal matrix notation storage area 560 is provided. Correspondingly, the main memory 40
In 0, a calculation program for simultaneous linear equations according to the present embodiment is stored. And
The central processing unit 300 obtains a solution of the simultaneous linear equations to be analyzed using the various analysis conditions input from the input device 100 in accordance with the calculation program stored in the main memory 400. The central processing unit 300 implements each function of the simultaneous linear equation calculation apparatus according to the present embodiment by executing the above-described calculation program stored in the main memory 400.

The calculation apparatus of the present embodiment configured as described above performs numerical calculation on the simultaneous linear equations to be analyzed by the following processing procedure.

FIG. 4 is a flowchart showing a processing procedure of numerical calculation performed by the calculation apparatus of the second embodiment shown in FIG. FIG. 5 is a flowchart showing a continuation of the numerical calculation processing procedure shown in FIG.

First, the central processing unit 300, via the input device 100, has m rows and m columns as a coefficient matrix when the simultaneous linear equations to be analyzed are expressed as a matrix as “coefficient matrix × unknown number vector = known number vector”. The analyst is prompted to input an n-by-n block N diagonal matrix having a square matrix as a unit component (step 300). Specifically, the central processing unit 300 prompts the analyst to input only the block N double diagonal component in the block N double diagonal matrix.

In step 300, the central processing unit 300 prompts the analyst to input a positive even value as the value n of the block N double diagonal matrix size, which is a unit component of the block N double diagonal matrix. The square matrix size value m is not particularly limited except that it is a natural number.

In the present embodiment, as described above, the value n of the size of the block N double diagonal matrix
As an input, a positive even number value is input, but other general natural numbers may be input. This will be described later.

Further, in step 300, the central processing unit 300, in response to the input of the block N diagonal matrix as the coefficient matrix described above, has n rows with an unknown vector of m rows and 1 column as a unit component as a block unknown vector. The analyst is prompted to input a block unknown vector of 1 column and an n row 1 column known vector having m rows and 1 column as a unit component as a block known vector.

Furthermore, in step 300, the input device 100 prompts the analyst to input various analysis conditions such as initial conditions and boundary conditions necessary for solving the simultaneous linear equations to be analyzed.

The central processing unit 300 then inputs the block size n diagonal matrix size value n, the square matrix size value m that is a unit component of the block N double diagonal matrix, the initial condition, And various analysis conditions such as boundary conditions are stored in an analysis condition storage area 510 of the sub memory 500.
Remember me.

Next, the central processing unit 300, from the simultaneous linear equations input as described above,
Block N double diagonal matrix notation as initial matrix notation

Is generated (step 310).

here,

Is

Is an n-by-n block N-diagonal matrix expressed as Here, the N double diagonal component of the block N double diagonal matrix (65) is a non-zero matrix of m rows and m columns input from the input device 100. All other components are zero matrices. The relationship between N and z follows the definition described first. That is, when N is an odd number of 3 or more, z = (N−1) / 2, and when N is an even number of 4 or more, z = N / 2.

And

Is

Is an n-by-1 block unknown vector represented as Here, the unit component of the formula (66)

Is

Is an unknown vector of m rows and 1 column.

Also,

Is

An n-by-1 block unknown vector represented by: Here, the unit component of the formula (68)

Is

Is a known vector of m rows and 1 column expressed as Various analysis conditions such as initial conditions and boundary conditions input from the input device 100 are introduced into the known number vector (69).

Then, the central processing unit 300 stores the block N double diagonal component of the block N double diagonal matrix (65) and the block known number vector (66) in the block N double diagonal matrix notation storage area of the sub memory 500. 560 stores it.

Next, the central processing unit 300 reads the N double diagonal component of the block N double diagonal matrix (65) from the block N double diagonal matrix notation storage area 560 of the sub memory 500, and reads the read N double pairs. A block N-fold diagonal matrix (65) generated from the corner components is a triple block matrix which is a 4 × 4 block square matrix.

(Block 320). Here, p is a positive even number that satisfies p = n / z.

As a result, the central processing unit 300 can generate a block tridiagonal matrix of p rows and p columns from a block N double diagonal matrix notation as an initial matrix notation.

Block tridiagonal matrix notation with as coefficient matrix

Is generated (step 330). This is substantially the same as the block tridiagonal matrix (2) in the first embodiment.

here,

Is

Is a block unknown vector of p rows and 1 column expressed as This is substantially the same as the block unknown vector (3) in the first embodiment. Here, the unit component of the formula (73)

Is

Is an unknown vector of z rows and 1 column expressed as This is substantially the same as the unknown vector (4) in the first embodiment.

Also,

Is

P × 1 block known vector represented as This is substantially the same as the block known number vector (5) in the first embodiment. Here, the unit component of the formula (75)

Is

Is a z-by-1 block known vector represented as This is substantially the same as the block known number vector (6) in the first embodiment.

Then, the central processing unit 300 stores the tridiagonal component of the block tridiagonal matrix (71) and the block known number vector (75) in the block tridiagonal matrix notation storage area 520 of the sub memory 500. Remember me.

In this way, the block N tridiagonal matrix notation which is the initial matrix notation in the second embodiment is converted to the block tridiagonal matrix notation in the first embodiment. It is possible to apply the solution process of steps 110 to 240 in one embodiment.

However, in the first embodiment, the value p of the block tridiagonal matrix size is a power of 2, whereas in the second embodiment, this size value p (= n / Z) is a positive even number, but is not necessarily a power of 2.

  Therefore, this point will be described below.

The central processing unit 300 reads the value p of the size of the block tridiagonal matrix (72) from the block tridiagonal matrix notation storage area 520 of the sub memory 500, and reads the read value p
To determine the number of divisions based on the power series expansion of 2 (multinomial)

Is used to calculate the natural number f _i (step 340). In formula (77), f _i ≦ 0
All values of f _i satisfying the above are set to 0.

The power series expansion of 2 is

The arbitrary natural number p can always be expanded as shown in Equation (78). Here, a _i (i = 0, 1, 2,..., F) = 1 or 0. Further, F is a natural number and i is a subscript as an index of each term, but a block tridiagonal matrix (7
Since the size value p in 2) is an even number, i = 0 is considered here.

Next, the central processing unit 300, each term p _i and term-specific parameter set in association with the natural numbers f _i of formula _{(77) (p i, f} i) (i = 1, ···, F) as The data is stored in the item-specific separation parameter set storage area 570 of the sub memory 500.

Next, the central processing unit 300 reads the block tridiagonal component of the block tridiagonal matrix from the block tridiagonal matrix display storage area 520 of the sub memory 500, and reads the read block tridiagonal component. A block tridiagonal matrix expression (72) is generated from the components.

Next, the central processing unit 300, Section-specific separation parameter set storage region 570 from section by separation parameter set of the sub-memory _{500 (p i, f i)} (i = 1,2, ···, F) reads , The read parameter p _i (i = 1, 2,..., F) as the separation size,
Block tridiagonal matrix notation (72)

 (Step 350).

The block tridiagonal matrix expression thus separated will be referred to as a separated block tridiagonal matrix expression. Further, the coefficient matrix of the separation block tridiagonal matrix notation represents the separation block tridiagonal matrix, the block unknown vector of the separation block tridiagonal matrix notation represents the separation block unknown vector, and the separation block triple. The block known number vector of the diagonal matrix notation is referred to as a separated block known number vector.

For example, the value p of the size of the read block tridiagonal matrix (72) is calculated using the division number determination polynomial (77).

It is assumed that In this case, the block tridiagonal matrix notation (72) is

That is,

When,

That is,

When,

That is,

Are separated into three diagonal blocks. In this case,
The term-specific separation parameter set is (p ₁ , f ₁ ), (p ₂ , f ₂ ), (p ₃ , f ₃ ).

Then, the central processing unit 300 uses the block tridiagonal components of the F separated block tridiagonal matrices and the F separated block triple known number vectors as the separated block tridiagonal matrix of the sub memory 500. It is stored in the notation storage area 580.

Next, the central processing unit 300 sets the initial value of the suffix i of the division target term, which is the term to be divided, to i = 1 (step 360).

Next, the central processing unit 300 reads the parameter f ₁ indexed by i = 1 from the item-specific separation parameter set storage area 570 of the sub memory 500, and sets this as the number of divisions (step 370).

Next, the central processing unit 300 adds the block tridiagonal component of the separated block tridiagonal matrix indexed with i = 1 from the separated block tridiagonal matrix notation storage area 580 of the sub memory 500. , Read the known vector of separated blocks, also subscripted with i = 1,
The processes of steps 140 to 180 in the first embodiment are performed.

Then, the central processing unit 300 increments the subscript value i of the item to be divided from i = 2 to F, thereby generating F separated compressed block matrix notations separated by terms (step 380, 390).

Next, the central processing unit 300 generates a combined block vector equation by taking out only the vector components of the boundary portion from the generated F separated compressed block matrix notations, and generates the combined block matrix notation (connected Block matrix x connected block unknown vector =
It is expressed as a matrix as a connected block known number vector) (step 400).

The central processing unit 300 stores the non-zero matrix component of the combined block matrix and the combined block known number vector in the combined block matrix notation storage area 590 of the sub memory 500.

Next, the central processing unit 300 reads a non-zero matrix component of the combined block matrix from the combined block matrix notation storage area 590 of the sub memory 500, and calculates an inverse matrix of the combined block matrix generated from the read non-zero matrix component. By calculating, the value of the vector component of the boundary portion is calculated (step 410). In the case of the above example,

Will be calculated. Note that what is performed in step 410 is the same as steps 210 to 240 in the first embodiment, and thus details thereof are omitted.

Next, the central processing unit 300 calculates the calculated boundary portion vector (in the above example,

) Are substituted into the original F separated compressed block matrix notation formulas (in the above example, formula (82), formula (84), formula (86)) to obtain F separated block matrixes. The expression is linearly separated (step 420). The separation block matrix notation that is linearly separated in this way is referred to as a complete separation block matrix notation.

Next, the central processing unit 300 calculates the inverse calculation solution of steps 210 to 240 in the first form for the compressed block matrix notation indexed with i = 1 in the F completely separated block matrix notations. Apply the process.

Then, the central processing unit 300 increments the subscript value i of the item to be divided from i = 2 to F, and recursively repeats the above process F-1 times (steps 390 and 395).
) To finally obtain the block unknown vector (73).

Needless to say, the second embodiment also includes the case where the value p of the block tridiagonal matrix size is expressed by the division number determination (unary) equation (7).

In step 340, the size value p of the block tridiagonal matrix (72) is determined by the division number determination (multinomial) equation (77).

When series expansion is performed as in step 360 to step 360 for the first term on the right side of equation (87).
Without performing the operations up to 400, the inverse matrix is directly calculated to extract the vector component of the boundary portion. Then, in step 410, the value may be calculated together with the vector component of the boundary portion extracted from the remaining terms.

For example, when p = 386, the block tridiagonal matrix notation stored in the block tridiagonal matrix notation storage area 520 of the sub memory 500 is

It is.

First, the central processing unit 300 reads the value p = 386 of the block tridiagonal matrix size from the analysis condition storage area 510 of the sub memory 500, and uses the read value p as a division number determination (polynomial) equation (77). )Using,

To expand the natural numbers f _i (i = 1, 2, 3) to f ₁ = 6 and f ₂ =, respectively.
5. Determine that f ₃ = 0 (step 340).

Next, the central processing unit 300 determines the size p _i (i = 1, 2) of each term on the right side of the equation (89).
, 3) and the natural numbers f _i (i = 1, 2, 3) in association with the term-specific separation parameter set (p _i ,
f _i ) = (256, 6), (128, 5), (2, 0) are stored in the item-specific separation parameter set storage area 570 of the sub memory 500.

Next, the central processing unit 300 reads the tridiagonal component of the block tridiagonal matrix from the block tridiagonal matrix notation storage area 520 of the sub memory 500, and from the read tridiagonal component. A block tridiagonal matrix notation (88) is generated.

Next, the central processing unit 300, Section-specific separation parameter set storage region 570 from section by separation parameter set of the sub-memory _{500 (p i, f i)} = (256,6), (128,5
), (2, 0) are read, and the read p ₁ = 256, p ₂ = 128, and p ₃ = 2 are set as separation sizes, and the block tridiagonal matrix expression (88) is divided into three separation block triples. Diagonal matrix notation

(Step 350).

The central processing unit 300 then separates the separated block tridiagonal matrix notations (90), (9
1) is subjected to the processing from step 360 onward, and the separation block tridiagonal matrix notation formula (
92), the inverse matrix of the coefficient matrix is directly applied as described above.

The vector component of the boundary is calculated by

After the process is taken out, the processing after step 410 may be performed. An existing numerical calculation program may be used for this processing. here,

It is.

It should be noted that the equation (95)

May be calculated from an algebraic relational expression similar to expression (11).

(Third embodiment)
FIG. 6 is a conceptual diagram showing a schematic configuration of a simultaneous linear equation calculation apparatus according to the third embodiment of the present invention. In addition, the same code | symbol is attached | subjected to the structure same as 2nd Embodiment, and repeated description is abbreviate | omitted.

The third embodiment assumes that the coefficient matrix of the simultaneous linear equations to be analyzed is a scalar q (q is an integer of 3 or more) multidiagonal matrix.

  In the following, q represents an integer of 3 or more.

As shown in FIG. 6, the computing device according to the third embodiment is similar to the second embodiment in that the input device 100, the output device 200, the central processing unit (CPU) 300, the main memory 400, The sub memory 500 is connected via an external bus 600.

The sub memory 500 according to the present embodiment includes a scalar q in addition to the storage area of the second embodiment.
A multi-diagonal matrix notation 595 is provided. Correspondingly, the main memory 400 contains
A calculation program for simultaneous linear equations according to the present embodiment is stored. Then, the central processing unit 300 obtains a solution of simultaneous linear equations to be analyzed using various analysis conditions input from the input device 100 in accordance with the calculation program stored in the main memory 400. The central processing unit 300 implements each function of the simultaneous linear equation calculation apparatus according to the present embodiment by executing the above-described calculation program stored in the main memory 400.

The calculation apparatus of the present embodiment configured as described above performs numerical calculation on the simultaneous linear equations to be analyzed by the following processing procedure.

FIG. 7 is a flowchart showing a processing procedure of numerical calculation performed by the calculation apparatus of the third embodiment shown in FIG. FIG. 8 is a flowchart showing a continuation of the numerical calculation processing procedure shown in FIG.

First, the central processing unit 300 uses the input device 100 as a coefficient matrix when a simultaneous linear equation to be analyzed is expressed as a matrix of “coefficient matrix × unknown number vector = known number vector”. The analyst is prompted to enter a scalar q multi-diagonal matrix (step 500).

Specifically, the input device 100 prompts the analyst to input only the scalar q multi-diagonal component of the scalar components of l rows and 1 columns of the above scalar multi-diagonal matrix.

In step 500, the central processing unit 300 prompts the analyst to input a positive even number as the size l of the scalar q multi-diagonal matrix.

In the present embodiment, as described above, a positive even value is input as the size value of the scalar q multi-diagonal matrix, but other general natural numbers may be input. . This will be described later.

Further, in step 500, the central processing unit 300 inputs the unknown vector of l rows and 1 column in response to the input of the scalar multidiagonal matrix as the coefficient matrix described above, and l
Prompt the analyst to enter a known vector of rows and columns.

Furthermore, in step 500, the central processing unit 300 prompts the analyst to input various analysis conditions such as initial conditions and boundary conditions necessary for solving the simultaneous linear equations to be analyzed. At that time, the central processing unit 300 prompts the analyst to input a positive even number smaller than l as the block m double diagonalization size value m.

In the present embodiment, as described above, a positive even number smaller than l is input as the block m double diagonalization size value m, but other general natural numbers are input. You may let them. This will also be described later.

Then, the central processing unit 300 subtracts various analysis conditions such as the size l of the scalar q-multidiagonal matrix, the size m of the block N-diagonalization, the initial condition, and the boundary condition input in this way. The data is stored in the analysis condition storage area 510 of the memory 500.

Next, the central processing unit 300, from the simultaneous linear equations input as described above,
Scalar q double diagonal matrix notation as initial matrix notation

Is generated (step 510).

here,

Is

Is a l-by-l scalar q-diagonal matrix expressed as Scalar q double diagonal matrix (97)
Is a non-zero scalar value input from the input device 100. All other components are zero. The relationship between q and z follows the definition described first. That is, when q is an odd number of 3 or more, z = (q−1) / 2, and when q is an even number of 4 or more,
z = q / 2.

And

Is

Is an unknown vector of 1 rows and 1 column expressed as

Also,

Is

Is a known vector of l rows and 1 column expressed as Note that various analysis conditions such as initial conditions and boundary conditions input from the input device 100 are introduced into the known number vector (99).

The central processing unit 300 then stores the scalar q multi-diagonal component of the scalar q multi-diagonal matrix (97) and the known number vector (99) in the scalar q multi-diagonal matrix notation storage area 595 of the sub memory 500. Remember me.

Next, the central processing unit 300 reads the block m double diagonalization size value m from the analysis condition storage area 510 of the sub memory 500, and converts the scalar q double diagonal matrix (97) to a square of m rows and m columns. Block is formed into an n-by-n block N-diagonal matrix in matrix units (step 5).
20). Here, n is a positive even number that satisfies n = 1 / m.

In this way, the central processing unit 300 calculates the block N double diagonal matrix display equation from the scalar q double diagonal matrix notation equation (96).

Is generated.

here,

Is

Is an n-by-n block N-diagonal matrix expressed as This is substantially the same as the block N double diagonal matrix (65) in the second embodiment. Here, the N double diagonal component of the block N double diagonal matrix (101) is a non-zero matrix of m rows and m columns. All other components are zero matrices.

And

Is

Is an n-by-1 block unknown vector represented as This is substantially the same as the block N double unknown vector (66) of the second embodiment. Here, the component of the formula (102)

Is

Is an unknown vector of m rows and 1 column.

Also,

Is

An n-by-1 block unknown vector represented by: This is substantially the same as the block N double known number vector (68) in the second embodiment. Where equation (104)
Ingredients

Is

Is a known vector of m rows and 1 column expressed as

In this way, the scalar q multi-diagonal matrix notation which is the initial matrix display formula in the third embodiment is converted into the block N double-diagonal matrix notation in the second embodiment. Thereafter, the solution process of steps 320 to 395 in the second embodiment can be applied.

  However, in the third embodiment, N = 3 may be possible.

Therefore, the central processing unit 300 determines whether or not N of the block N double diagonal matrix (101) is an integer equal to or greater than 4 (step 530). Here, if it is determined that N is 4 or more, the process proceeds to step 320 to convert the block N diagonal matrix (101) into a block tridiagonal matrix, and the process proceeds to the next step. . In step 530, N is 3
If it is determined that, the process proceeds to step 530.

Thereafter, the central processing unit 300 can finally obtain the unknown vector (98) by performing the processing of steps 340 to 450 shown in FIGS.

In addition, what is necessary is just to use the existing numerical calculation program for the judgment process in step 530. FIG.

In this embodiment (first to third embodiments), as values of various sizes, a value of power of 2 as a value p of the size of a block tridiagonal matrix (first embodiment), a block N
As a value n of a positive diagonal matrix, a positive even number (second embodiment), as a positive value as a size q of a scalar q double diagonal matrix, and as a value m of a block N double diagonalization size Although it is assumed that the input of a positive even number (third embodiment) smaller than 1 is prompted, a general natural number may be input to these values.

For example, in the first embodiment, when a natural number is simply input as the value p of the block tridiagonal matrix size, instead of the division number determination formula (7) in the division number determination process, The division number determination formula (77) in the second embodiment (strictly, the formula (7
8)) may be used. Since the case where the value of p is an even number has already been described in the second embodiment, the case where the value of p is an odd number will be briefly described here.

For example, when p = 387, the block tridiagonal matrix notation stored in the block tridiagonal matrix notation storage area 520 of the sub-memory 500 is

It is.

First, the central processing unit 300 reads the value p = 387 of the block tridiagonal matrix size from the analysis condition storage area 510 of the sub memory 500, and uses the read value p as a division number determination (polynomial) equation (77). )Using,

And the natural number f _i (i = 1, 2, 3) is converted into f ₁ = 6 and f ₂ = respectively.
5, f ₃ = 0 is determined (step 340).

Next, the central processing unit 300 determines the size p _i (i = 1, 1) of each term on the right side of the equation (107).
2, 3) and the natural number f _i (i = 1, 2, 3) are related to each other and the separation parameter set for each term (p _i
, F _i ) = (256, 6), (128, 5), (3, 0), it is stored in the item-specific separation parameter set storage area 570 of the sub memory 500.

Next, the central processing unit 300 reads the tridiagonal component of the block tridiagonal matrix from the block tridiagonal matrix notation storage area 520 of the sub memory 500, and from the read tridiagonal component. A block tridiagonal matrix notation (106) is generated.

Next, the central processing unit 300, Section-specific separation parameter set storage region 570 from section by separation parameter set of the sub-memory _{500 (p i, f i)} = (256,6), (128,5
), (3, 0), and the read p ₁ = 256, p ₂ = 128, and p ₃ = 3 are set as separation sizes, and the block tridiagonal matrix notation (106) is converted into three separation block triples. Diagonal matrix notation

(Step 350).

The central processing unit 300 then uses the separation block tridiagonal matrix notation (108), (
109) is processed after step 360, and for the separated block tridiagonal matrix notation (109), the inverse matrix of the coefficient matrix is directly applied as described above.

The vector component of the boundary is calculated by

After the process is taken out, the processing after step 410 may be performed. An existing numerical calculation program may be used for this processing. here,

It is.

Note that the equation (113)

May be calculated from an algebraic relational expression similar to expression (11).

For example, when p = 385, the block tridiagonal matrix notation stored in the block tridiagonal matrix notation storage area 520 of the sub memory 500 is

It is.

First, the central processing unit 300 reads the value p = 385 of the block tridiagonal matrix size from the analysis condition storage area 510 of the sub memory 500, and uses the read value p as a division number determination (polynomial) equation (77). )Using,

And the natural number f _i (i = 1, 2, 3) is converted into f ₁ = 6 and f ₂ = respectively.
5, f ₃ = 0 is determined (step 340).

Next, the central processing unit 300 determines the size p _i (i = 1, 1) of each term on the right side of the equation (115).
2, 3) and the natural number f _i (i = 1, 2, 3) are related to each other and the separation parameter set for each term (p _i
, F _i ) = (256, 6), (128, 5), (1,0) are stored in the item-specific separation parameter set storage area 570 of the sub memory 500.

Next, the central processing unit 300 reads the tridiagonal component of the block tridiagonal matrix from the block tridiagonal matrix notation storage area 520 of the sub memory 500, and from the read tridiagonal component. A block tridiagonal matrix notation (114) is generated.

Next, the central processing unit 300, Section-specific separation parameter set storage region 570 from section by separation parameter set of the sub-memory _{500 (p i, f i)} = (256,6), (128,5
), (1,0), and the read p ₁ = 256, p ₂ = 128, and p ₃ = 1 are set as separation sizes, and the block tridiagonal matrix notation (114) is converted into three separation block triples. Diagonal matrix notation

(Step 350).

The central processing unit 300 then uses the separation block tridiagonal matrix notation (116), (
117) is processed after step 360, and for the separated block tridiagonal matrix notation (118), the coefficient matrix is a 4 × 4 scalar square matrix. Vector component of boundary part by directly calculating inverse matrix

After the process is taken out, the processing after step 410 may be performed. An existing numerical calculation program may be used for this processing.

As is clear from the above description, the most important thing in the present invention is that when the block tridiagonal matrix is divided using a 4-by-4 block square matrix as a unit of division and the inverse matrix is obtained, The point lies in using a specific algebraic relation obtained by paying attention to the existence of the zero matrix. As a result, the processing time can be significantly shortened compared with the normal calculation method of the inverse matrix in the conventional calculation apparatus.

That is, in the calculation device described in Patent Document 1, the inverse matrix calculation associated with the division process is calculated using a conventional calculation method, whereas in the calculation device of the present invention, the division unit is 4. By limiting to a block square matrix with 4 rows and columns, the algebraic relational expression as described above can be used when calculating the inverse matrix. As a result, when compared with the calculation method described in Patent Document 1, it is clear that the calculation amount is smaller when calculating the inverse matrix.

Furthermore, in the present embodiment (first to third embodiments), it is assumed that all block tridiagonal components of the block tridiagonal matrix are different, but in the actual calculation, on the diagonal line. The block matrix components are all the same matrix, the block matrix components above (right) on the diagonal are all the same matrix, and the block matrix components below (left) on the diagonal are often all the same matrix. In that case, the block tridiagonal matrix is substantially composed of three types of block matrix components, and the effect of the present invention becomes more remarkable. This is because all the divided block triple matrices are the same in the divided block triple matrix notation, and therefore, it is only necessary to calculate one divided block triple matrix notation. In this case, the specific algebraic relational expression is greatly simplified, so that the calculation time can be further reduced.

  In order to clarify the above effects, specific calculation results using the calculation method according to the first embodiment of the present invention will be shown.

As an example, in a parallelogram area on a two-dimensional plane, physical quantities of scalar variables

Laplace equation for

Is solved using the finite element method. The Laplace equation is an elliptic partial differential equation describing a static equilibrium state such as a thermal equilibrium state of a heat conduction phenomenon or a stationary phenomenon. In this example, a parallelogram ABCD having long sides and short sides of a, b, ｂABC = 120 ° and ∠BCD = 60 ° is represented by 2 (p + 1) (z + 1) as shown in FIG. It is divided into a single unit (regular triangle), and each node is set to (i, j) (where i = 0, 1,..., P + 1, j = 0, 1,..., Z + 1, p ≧ z ) On the numbered area. At this time, the physical quantity

On each node

(Where i = 0, 1,..., P + 1, j = 0, 1,..., Z + 1, p ≧ z). In this example, p = 256 and z = 100 are set as analysis conditions. Under this assumption, when the two-dimensional Laplace equation (120) is discretized by the finite element method, a block tridiagonal matrix notation corresponding to equation (1) is obtained.

Get.

Here, it corresponds to equation (2)

Is

Is a block tridiagonal matrix of 256 rows and 256 columns and each block tridiagonal component

Respectively

As a 100 × 100 square matrix.

Also, it corresponds to equation (3)

Is

Is a block unknown vector of 256 rows and 1 column expressed as: a unit component of the equation (124) corresponding to the equation (4)

Is

Is an unknown vector of 100 rows and 1 column expressed as

Moreover, it respond | corresponds to Formula (5).

Is

Is a block known vector of 256 rows and 1 column expressed as Here, the unit component on the right side of Expression (126)

Is

Is a known vector of 100 rows and 1 column expressed as In this example, as the block known number vector of the equation (126) representing the boundary condition,

Is set (directive boundary condition).

  The central processing unit 300 then represents the block tridiagonal matrix component (123) of the block tridiagonal matrix (122) and the block known number vector (126) in the block tridiagonal matrix notation of the sub memory 500. Store in the formula storage area 520.

Next, the central processing unit 300 reads the value p = 256 of the size of the block tridiagonal matrix (122) from the analysis condition storage area 510 of the sub memory 500, and from this value and the division number determination formula (7).

A natural number f = 6 that satisfies the above is obtained (step 120), and this value is set as the upper limit of the number r of divisions (step 130).

Next, the central processing unit 300 sets the initial value of the division number r to r = 1 and starts the first division process (step 140). In the case of this example, the central processing unit 300 converts the block tridiagonal matrix notation (121) into a first divided block matrix which is a 4 × 4 block square matrix.

As a unit

Blocks are equally divided (step 150). In step 160, the central processing unit 300 directly corresponds to the equation (10) by directly substituting the block tridiagonal component of the first divided block matrix (130) into the first algebra relation (11). A first divided block inverse matrix is calculated. Thereafter, the processing of steps 170 to 200 in FIG. 2 is repeated until r = 6, and then the processing after step 210 is performed to calculate the block unknown vector (124).

FIG. 10 shows the result of calculating this processing with a general-purpose personal computer using mathematical expression calculation software Mathematica. Real time required to obtain this calculation result

Is the real time when this example is optimally calculated by the calculation method described in Patent Document 1.

Both as a linear function of p

Can be evaluated. Furthermore, when z = 100,

From the equations (131) and (132),

It turns out that it becomes. In this example, p = 256. However, when p is larger, it can be seen from Formula (133) that the calculation time can be shortened by about 7 times compared with the calculation method of Patent Document 1.

The reason why such a reduction in calculation time can be expected in the present invention when compared with Patent Document 1 is that when the inverse matrix is obtained in steps 160 and 210, the inverse matrix is directly calculated using a predetermined algebraic relational expression. Due to that. Also, as in this example, the main diagonal components of the block tridiagonal matrix are all matrix

And all of the diagonal components above and below are matrix

,line; queue; procession; parade

In the case of a good quality matrix (122), the divided block matrixes at the respective division stages are all the same matrix, so that the divided block inverse matrix need only be obtained once. Similarly, in step 210, the compressed block inverse matrix need only be obtained once. On the other hand, in the calculation method of Patent Document 1, since the conventional method is used for all the inverse matrix calculations, a considerable amount of calculation time is consumed even in the case of this example. It is clear that this difference becomes even more pronounced when the value of p is large.

  In addition, it is desirable that the various division and compression processes of this embodiment be performed in parallel calculation processing using a plurality of central processing units. In this regard, in the computing device of the present embodiment shown in FIG. 1, an external bus is assumed as the bus 600. However, by using an expansion bus for the bus 600, a central processing unit of a plurality of computers can be used. It is also possible to execute a calculation program for simultaneous linear equations according to the invention. Of course, it is possible to process various divisions and compression processes using a single central processing unit using a time sharing method, or to apply a time sharing method to a plurality of central processing units. Obviously, a processing + time sharing method may be used.

  The simultaneous linear equation calculation program according to the present invention includes a magneto-optical disk such as MO, MD, DATA, and ID format, an optical disk such as CD-R, CR-RW, DVD-RAM, and DVD-RW, a flexible disk, The recording can be performed on a computer-readable recording medium such as a magnetic disk such as zip or super disk, a magnetic tape, a memory stick, smart media, or a flash memory such as a PC card. The computer can solve the simultaneous linear equations having a general multi-diagonal matrix as a coefficient matrix in a short time by reading the calculation program recorded in these storage media.

  The analysis procedure shown in the present embodiment is provided to the computer via the various recording media described above, and lines such as the Internet and an intranet. Thus, the computer can solve the simultaneous linear equations having a general multi-diagonal matrix as a coefficient matrix in a short time by executing the above-described simultaneous linear equation calculation program.

It is the conceptual diagram which showed schematic structure of the calculation apparatus of simultaneous linear equations which concerns on the 1st Embodiment of this invention. It is a flowchart which shows the process sequence of the numerical calculation performed with the computer apparatus shown in FIG. It is the conceptual diagram which showed schematic structure of the calculation apparatus of simultaneous linear equations which concerns on the 2nd Embodiment of this invention. It is a flowchart which shows the process sequence of the numerical calculation performed with the calculation apparatus shown in FIG. 5 is a flowchart showing a continuation of the numerical calculation processing procedure shown in FIG. 4. It is the conceptual diagram which showed schematic structure of the calculation apparatus of simultaneous linear equations which concerns on the 3rd Embodiment of this invention. It is a flowchart which shows the process sequence of the numerical calculation performed with the calculation apparatus shown in FIG. It is a flowchart which shows the continuation of the process sequence of the numerical calculation shown in FIG. It is a figure which shows a mode that the parallelogram area | region was divided | segmented into single (regular triangle). It is a graph which shows the result of having carried out the numerical calculation of the Laplace equation on the area | region shown in FIG. 9, using the solution method of the simultaneous linear equations which concerns on the 1st Embodiment of this invention.

Explanation of symbols

Input device 100
Output device 200
Central processing unit 300
Main memory 400
Sub memory 500
Analysis condition storage area 510
Block tridiagonal matrix notation storage area 520
First divided block inverse matrix storage area 540 ₁
First compressed block matrix notation storage area 550 ₁
R-th divided block inverse matrix storage area 540 _r
R-th compressed block matrix notation storage area 550 _r
F (final) divided block inverse matrix storage area 540 _f
F (final) compressed block matrix notation storage area 550 _f
Block N double diagonal matrix notation storage area 560
Item-specific separation parameter storage area 570
Separate block tridiagonal matrix notation storage area 580
Combined block matrix notation storage area 590
Scalar q multi-diagonal matrix notation storage area 595
External bus 600

Claims (7)

Computer to solve simultaneous linear equations,
Coefficient matrix input means for prompting input of a block tridiagonal matrix having a square matrix as a coefficient matrix of the simultaneous linear equations;
A block tridiagonal that generates a block tridiagonal matrix notation (block tridiagonal matrix × block unknown vector = block known vector) from the simultaneous linear equations based on the input of the block tridiagonal matrix Matrix expression generation means;
Division number determination means for determining the number of divisions from the size of the block tridiagonal matrix;
A block matrix for dividing the block tridiagonal matrix notation into a plurality of divided block matrix notations (divided block matrix × divided block unknown vector = divided block known number vector) in units of a 4 × 4 block square matrix A notation dividing means;
A divided block inverse matrix computing means for computing a divided block inverse matrix that is an inverse matrix of the plurality of divided block matrices using a predetermined algebraic relational expression;
From the plurality of divided block unknown vectors, the plurality of divided block known vectors, and the plurality of divided block inverse matrices, a plurality of renormalization block matrix expressions (divided block unknown vector = divided block inverse matrix × divided block renormalization) Renormalization block matrix expression generating means for generating (vector),
A compressed block matrix that generates a compressed block matrix notation (compressed block matrix × compressed block unknown vector = compressed block renormalization vector) by extracting and compressing only vector components located at the boundaries of the plurality of renormalization block matrix notations A notation generation means;
Recursive operation control means for recursively repeating the operations from the division to the compression on the compressed block matrix notation, with the determined number of divisions as an upper limit,
A plurality of divided blocks generated by the divided block inverse matrix generation unit are used as the values of the compressed block unknown vector in all the compressed block matrix notations obtained by the recursive operation control unit repeated up to the upper limit of the number of divisions. A reverse calculation solution means for obtaining an inverse matrix by applying the inverse matrix in the reverse order to the operation from the division to the compression;
A simultaneous linear equation calculation program that allows them to function. 2. The simultaneous primary according to claim 1, wherein the division number determining means determines the number of divisions based on the order of each term when the size of the block tridiagonal matrix is expanded to the power of 2. Equation calculation program. The division number determining means determines the number of divisions as a natural number f satisfying the relational expression p = 2 ^{f + 2} when the size of the block tridiagonal matrix is p. 3. A program for calculating simultaneous linear equations according to item 1 or 2. A computing device for solving simultaneous linear equations,
Coefficient matrix input means for prompting input of a block tridiagonal matrix having a square matrix as a coefficient matrix of the simultaneous linear equations;
A block tridiagonal that generates a block tridiagonal matrix notation (block tridiagonal matrix × block unknown vector = block known vector) from the simultaneous linear equations based on the input of the block tridiagonal matrix Matrix expression generation means;
Division number determination means for determining the number of divisions from the size of the block tridiagonal matrix;
A block matrix for dividing the block tridiagonal matrix notation into a plurality of divided block matrix notations (divided block matrix × divided block unknown vector = divided block known number vector) in units of a 4 × 4 block square matrix A notation dividing means;
A divided block inverse matrix computing means for computing a divided block inverse matrix that is an inverse matrix of the plurality of divided block matrices using a predetermined algebraic relational expression;
From the plurality of divided block unknown vectors, the plurality of divided block known vectors, and the plurality of divided block inverse matrices, a plurality of renormalization block matrix expressions (divided block unknown vector = divided block inverse matrix × divided block renormalization) Renormalization block matrix expression generating means for generating (vector),
A compressed block matrix that generates a compressed block matrix expression (compressed block matrix × compressed block unknown vector = compressed block renormalization vector) by extracting and compressing only the vector components located at the boundary portions of the plurality of renormalization block matrix expressions A notation generation means;
Recursive operation control means for recursively repeating the operations from the division to the compression on the compressed block matrix notation, with the determined number of divisions as an upper limit,
A plurality of divided blocks generated by the divided block inverse matrix generation unit are used as the values of the compressed block unknown vector in all the compressed block matrix notations obtained by the recursive operation control unit repeated up to the upper limit of the number of divisions. A reverse calculation solution means for obtaining an inverse matrix by applying the inverse matrix in the reverse order to the operation from the division to the compression;
A system for calculating simultaneous linear equations. A calculation method for solving simultaneous linear equations using a computer,
A first step for prompting input of a block tridiagonal matrix having a square matrix as a coefficient matrix of the simultaneous linear equations;
A second step of generating a block tridiagonal matrix notation (block tridiagonal matrix × block unknown vector = block known vector) from the simultaneous linear equations based on the input of the block tridiagonal matrix;
A third step of determining the number of divisions from the size of the block tridiagonal matrix;
The block tridiagonal matrix notation is divided into a plurality of divided block matrix notations (divided block matrix × divided block unknown vector = divided block known number vector) in units of a 4 × 4 block square matrix. Steps,
A fifth step of calculating a divided block inverse matrix that is an inverse matrix of the plurality of divided block matrices using a predetermined algebraic relational expression;
From the plurality of divided block unknown vectors, the plurality of divided block known vectors, and the plurality of divided block inverse matrices, a plurality of renormalization block matrix expressions (divided block unknown vector = divided block inverse matrix × divided block renormalization) A sixth step of generating (vector),
A seventh step of generating a compressed block matrix notation (compressed block matrix × compressed block unknown vector = compressed block renormalization vector) by extracting and compressing only vector components located at the boundary portions of the plurality of renormalization block matrix notations When,
An eighth step of recursively repeating the fourth step to the seventh step with respect to the compressed block matrix notation, with the determined number of divisions as an upper limit;
The value of the compressed block unknown vector in all the compressed block matrix notations obtained by repeating up to the upper limit of the number of divisions in the eighth step, and the plurality of divided block inverse matrices generated in the fifth step A ninth step determined by performing in the reverse order to the operation from division to compression;
Method for solving simultaneous linear equations consisting of 6. The simultaneous primary according to claim 5, wherein in the third step, the number of divisions is determined based on the order of each term when the size of the block tridiagonal matrix is expanded to the power of 2. Equation solving method. The number of divisions is determined as a natural number f satisfying the relational expression p = 2 ^{f + 2} when the size of the block tridiagonal matrix is p in the third step. 7. A method for solving simultaneous linear equations according to item 5 or 6.

Images