Method and medium for operating a vector computer

Details Method and medium for operating a vector computer Method and medium for operating a vector computer

1999-06-18

2002-09-03

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S443000

Reexamination Certificate

active

06446105

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method of operating a vector computer in order to solve an equation including matrix.
2. Description of the Related Art
In the past, the following differential equations (1) to (3) are known in solution of boundary value problems.
In particular, in the case of elliptical partial differential equations, these equations are often used.
A q=r
  (1)
(&Dgr;−
L
)
p=r
  (2)
&Dgr;
−1
(&Dgr;−
U
)−
L
)
q=p
  (3)
Where, A is an m×m matrix, &Dgr; is an m×m diagonal matrix, L is a lower m×m matrix, and U is an upper m×m matrix, and where p, q and r are respectively vectors of the dimension m.
These boundary value problems arise in a plurality of numerical calculations of technical magnitudes, such as in the calculation of temperature distribution in a three-dimensional body, or calculation of a fluid flow about a given geometric shape. A further simple example is the solution of the Poisson equation with Dirichlet boundary conditions.
Normally, for the numerical solution of the problems, discrete variable method is used, the space in which the solution is to be calculated is covered by a point lattice, and in which then a solution for each lattice point is calculated numerically.
For this purpose, the solution function about each lattice point may be developed into a Taylor series, and then the differential quotients can be replaced by difference quotients. In order to calculate an approximate solution at a lattice point, knowledge of the approximate solution at the adjacent lattice points is sufficient if the remainders of the series development are negligible. Such a method is disclosed for example in “Numerische Mathematik für Ingenieure und Physiker” W. Tornig, Volume 2, Springer-Verlag, Berlin.
For example it may be sufficient in a two-dimensional space with a square grid to know the solution at the directly adjacent four lattice points, in order to calculate the approximate solution at the lattice point surrounded by these four lattice points.
FIG. 1
shows a so-called 5-point stencil being used in relation to this case. While in
FIG. 2
, a 7-point stencil is shown as the corresponding case for three-dimensional space.
By applying the approach described above, with appropriate numbering of the lattice points, to the shown 7-point stencil, the problems may be represented as follows:
a
ijk,1
q
ijk−1
+a
ijk,2
q
ij−1k
+a
ijk,3
q
i−ljk
+a
ijk,4
q
ijk
+a
ijk,5
q
i+1jk
+a
ijk,6
q
ij+1k
+a
ijk,7
q
iljk+1
=r
ijk
  (4)
For each lattice point (ijk) from the set G with
G
={(
ijk
)1
<=i<=n
x
, 1<=
j←n
y
, 1←
k←n
z
}  (
5)
Where, n
x
, n
y
, and n
z
are the number of lattice points in x, y, and z axis directions, respectively.
With appropriate selection of the numbering of the lattice points, the matrix A usually contains only a few extra-diagonal elements which are different from zero.
Equation (1) shown above is then not directly solved, but firstly, using relation of equation (6) and preconditioner (7), is converted into the equation (8).
A=D−L−U
  (6)
M=P
1
×P
2
  (7)
(
P
1
−1
A P
2
−1
)(
P
2
q
)=
P
1
−1
r
  (8)
Where, D is the diagonal matrix from the elements of the diagonals of the original matrix A.
A frequently used and successful preconditioner is so-called “incomplete lower upper preconditioner” (ILU preconditioner).
Also, the following equation holds.
M=
(&Dgr;−
L′
)&Dgr;
−1
(&Dgr;−
U′
)  (9)
Thus, &Dgr;=D−diagonal elements (L&Dgr;
31 1
U)−&agr; line total (extra-diagonal elements (L&Dgr;
−1
U)) with 0<=&agr;<=1; extra-diagonal elements (F)=F−diagonal elements (F); and the line total means a diagonal matrix in which each element of the diagonals corresponds to the sum of the elements of the same line.
This is the known Gustavson acceleration (I. Gustafson) “A Class of First Order Fracturization Methods”, BIT 18 (1978), pages 142-156). The matrices U′ and L′ are identified in equation (9) with an apostrophe, in order to indicate that they are not necessarily identical to the matrices U and L from equation (6), although this is the case in the ILU approach described. Appropriate alternations to the matrix U′ and L′ can lead to improved convergence.
In order to determine &Dgr; in equation (9), there are further approaches, roughly the SSOR approach with &Dgr;=D. Preconditioning corresponds to the solution of the following linear equation (10).
M q=r
  (10)
Where, r is the known vector. A schematic view of this equation is shown in FIG.
3
. The solution can be obtained by solving the equations (11) and (12).
(&Dgr;−
L
)
p=r
  (11)
&Dgr;
−1
(&Dgr;−
U
)
q=p
  (12)
If the initial problem was aligned on a structured grid, the elements which are different from zero of the matrices U and L can be arranged regularly. For example, in the case of the 7 point stencil in the regular three-dimensional grid points each of which is included in the above set G and has a lexicographic number of the grid points in the matrix L, elements which are different from zero are present only in the first secondary diagonal, in the n
x
-th secondary diagonal and in the (n
x
n
y
) th secondary diagonal. In other words, only the elements at L
i,i−1
, L
i,i−nx
and L
i,i−nx ny
are different from zero.
Here, the n-th secondary diagonal means a sequence which includes elements aligned parallel to a sequence of primary diagonal elements (L
1,1
, L
2,2
, . . . ) and is the n-th sequence from the primary diagonal elements.
The equations (11) and (12) can be solved by corresponding forward or reverse substitutions.
p=&Dgr;
−1
(
r−L p
)  (13)
q=p−&Dgr;
−1
U q
  (14)
An example of pseudo code of an algorithm (1) for these substitutions is shown in FIG.
4
.
This method is known as the hyperplane method. It can be shown that hyperplanes can be constructed from lattice points and the lattice points can be calculated independently of one another. This is because that the solution at any optional lattice point of the hyperplane is not dependent on the solution of any other point on the same plane.
Corresponding hyperplanes for three-dimensional space are shown in FIG.
5
. The following equation may be applied to the 7-point stencil.
H
(
l
)={
i=i
x
+(
i
y
−1)
n
x
+(
i
z
−1)
n
x
n
y
|i
x
+i
y
+i
z
=l
+2}(1
<=l<=nl=n
x
+n
y
+n
z
−2)  (15)
The disadvantage of this method resides mainly in the fact that the efficiency of a queue processing or a vector processing in a vector processor is greatly reduced by the indirect addressing in the above described algorithm (1).
It would be more advantageous to be able to access the memory always with a constant stride (see also “Computer Architecture.”, Computational Science Education Project, Section 3.3.1 “Interleaved Memory”).
Moreover the method is not suitable for computers with divided parallel memory blocks and a plurality of vector processors, as no parallelism occurs relative to magnitude of the hyperplane, and as many hyperplanes H(l) alone are too small to be logically distributed between a plurality of processors. Furthermore, in the known hyperplane method, no generalization to higher-dimensional spaces or stencils other than the known 5-point or 7-point stencils is known. An approach in order to counter these problems is not to solve the equations (11) and (12) exactly, but to calculate an approximate solution by iteration. Normally, a von-Neumann series developme

Affiliated with

Also associated with

Rating

Method and medium for operating a vector computer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and medium for operating a vector computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and medium for operating a vector computer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2856265