Finite element analysis method using multiprocessor for matrix manipulations with special handling of diagonal elements

Claim 2

Apparatus for loading and storing a matrix defined by a series of one dimensional arrays arranged along orthogonal axes, comprising: a plurality of processing cells, said cells being intercoupled to pass data therebetween; a memory for each said processing cell; means for scanning each element of said matrix along one orthogonal axis thereof; means for loading non-zero elements of said matrix along said one orthogonal axis into the respective memories of a plurality of said cells, said means for loading including means for loading all of the non-zero diagonal elements of said matrix into the memory of a designated one of said cells; and means for generating an index, said index being stored in association with each such stored non-zero element for identifying the array along said other axis from which said non-zero element originated.

Claim 3

The combination of claim 1 wherein said means for loading comprises means for loading consecutive non-zero, non-diagonal elements into consecutive processing cells.

Claim 4

The combination recited in claim 2 further including means for concurrently operating on said stored elements with a plurality of previously determined to generate intermediate results; and means for storing said intermediate results at each cell according to said index.

Claim 5

The combination recited in claim 3 further including: means for processing said intermediate results from a plurality of processing cells based on said index.

Claim 6

The combination recited in claim 4 wherein said means for operating on said stored elements comprises means for multiplying each stored non-diagonal element originating from a given column of the matrix by a common element of a second matrix.

Claim 7

Apparatus for loading and storing a matrix on a parallel processor comprising a plurality of processing cells, each cell having a memory, comprising: means for storing elements of a matrix in the memories of a plurality of said cells, said means for storing including means for storing all non-zero diagonal elements of said matrix in the memory of one of said cells; and means for generating and storing in association with each stored element an index for identifying a one dimensional array of said matrix from which said stored element originates.

Claim 8

Apparatus for loading and storing a matrix on a parallel processor comprising a plurality of processing cells, each cell having a memory, comprising: means for storing elements of a matrix in the memories of a plurality of said cells, said means for storing including means for storing all non-zero diagonal elements of said matrix in the memory of one of said cells; and means for generating and storing in association with each stored element an index for identifying a one dimensional array of said matrix from which said stored element originates.

Claim 9

The combination recited in claim 6 further including: means for performing a matrix operation on said stored elements to generate intermediate results; means for accumulating said intermediate results at each cell according to said index; and means for processing said intermediate results from a plurality of processing cells based on said index.

Claim 10

The combination recited in claim 7 wherein said matrix includes a plurality of rows and columns and wherein said means for storing further comprises means for scanning each column of said matrix, disregarding zero elements, and storing non-zero elements in the respective memories of a plurality of said cells, the stored elements of each column forming different transpose vectors.

Claim 11

The combination recited in claim 8 wherein said index identifies the row of said matrix from which each stored element originates.

Claim 12

The combination recited in claim 9 wherein said means for performing a matrix operation comprises means for multiplying each stored non-diagonal element of said transpose vector by a common operand.

Claim 13

The combination recited in claim 10 wherein said multiplying means further includes means for successively multiplying different elements of a given transpose vector by the same element of a second vector at a plurality of processing cells.

Claim 14

The combination recited in claim 11 further including means for accumulating the partial results generated at each processor cell according to said index.

Claim 15

The combination recited in claim 12 further including means for accumulating the partial results from multiplication operations at each cell according to said index.

Claim 16

In a process for analyzing a physical system which can be defined by certain physical variables capable of being expressed in terms of a plurality of linear equations solvable by matrix manipulation methods, a machine implemented method for loading and storing a matrix of elements which relate said variables to each other onto a parallel processor which includes a plurality of processing cells, each cell having a memory, the matrix being comprised of a series of one dimensional arrays of said elements along orthogonal axes, the method comprising the steps of: scanning said arrays of said matrix along one orthogonal axis thereof; loading non-zero elements of said matrix along said one orthogonal axis into the respective memories of a plurality of said cells, all of said non-zero diagonal elements of said matrix being loaded into a designated one of said cells; and generating for storage in association with each such stored non-zero element an index for identifying the array along said other axis from which said non-zero element originated.

Claim 17

In a process for analyzing a physical system which can be defined by certain physical variables capable of being expressed in terms of a plurality of linear equations solvable by matrix manipulation methods, a machine implemented method for loading and storing a matrix of elements which relate said variables to each other onto a parallel processor which includes a plurality of processing cells, each cell having a memory, the matrix being comprised of a series of one dimensional arrays of said elements along orthogonal axes, the method comprising the steps of: scanning said arrays of said matrix along one orthogonal axis thereof; loading non-zero elements of said matrix along said one orthogonal axis into the respective memories of a plurality of said cells, all of said non-zero diagonal elements of said matrix being loaded into a designated one of said cells; and generating for storage in association with each such stored non-zero element an index for identifying the array along said other axis from which said non-zero element originated.

Claim 18

The method of claim 14 wherein said loading comprises the steps of loading consecutive non-zero non-diagonal elements into consecutive processing cells.

Claim 19

The method of claim 14 including the further step of successively operating on said stored elements in each cell with a plurality of previously determined operands to generate intermediate results in each cell; and storing said intermediate results in said cell according to said index.

Claim 20

The method of claim 16 further including the step of: processing said intermediate results from a plurality of processig cells according to said index.

Claim 21

The method of claim 17 wherein said step of successively operating on said stored elements comprises successively multiplying each stored non-diagonal element originating from the same column of sid matrix by the same element of a second matrix.

Claim 22

In a process for analyzing a physical system which can be defined by certain physical variables capable of being expressed in terms of a plurality of linear equations solvable by matrix manipulation methods, a machine implemented method for loading and storing a matrix of elements which relate said variables to each other onto a parallel processor which includes a plurality of processing cells, each cell having a memory, the matrix being comprised of a series of one dimensional arrays of said elements along orthogonal axes, the method comprising the steps of: storing elements of said matrix in the memories of a plurality of said cells, diagonal elements of said matrix being stored in a designated one of said cells; and generating for storage in association with each stored element an index for identifying the array along one axis of said matrix from which said stored element originates.

Claim 23

In a process for analyzing a physical system which can be defined by certain physical variables capable of being expressed in terms of a plurality of linear equations solvable by matrix manipulation methods, a machine implemented method for loading and storing a matrix of elements which relate said variables to each other onto a parallel processor which includes a plurality of processing cells, each cell having a memory, the matrix being comprised of a series of one dimensional arrays of said elements along orthogonal axes, the method comprising the steps of: storing elements of said matrix in the memories of a plurality of said cells, diagonal elements of said matrix being stored in a designated one of said cells; and generating for storage in association with each stored element an index for identifying the array along one axis of said matrix from which said stored element originates.

Claim 24

The method of claim 19 wherein said matrix includes a plurality of rows and columns and said storing includes the steps of scanning each element of each column of said matrix, disregarding zero elements, and storing scanned non-zero elements in memory locations associated with a plurality of said cells, the stored elements of each column forming different transpose vectors.

Claim 25

The method of claim 20 wherein said index identifies the row of said matrix from which each said non-zero element originates.

Claim 26

The method of claim 21 further including the steps of: performing a matrix operation on said stored elements to generate intermediate results; storing said intermediate results according to said index; and processing said intermediate results from a plurality of processing cells according to said index.

Claim 27

The method of claim 22 wherein the step of performing a matrix operation comprises multiplying each stored non-diagonal element of a given transpose vector by corresponding element of a second vector.

Claim 28

The method of claim 23 wherein said multiplying takes place by moving each element of said second vector into each processor cell to be multiplied by a different element from the corresponding one of said transpose vectors.

Claim 29

The method of claim 23 wherein the results of said multiplying steps are accumulated according to said index at each processor cell.

Claim 30

The method of claim 25 including the further step of accumulating the results from said cells according to said index.

Claim 31

In a process for analyzing a physical system which can be defined by certain physical variables capable of being expressed in terms of a plurality of linear equations solvable by matrix manipulation methods, a machine implemented method for loading and storing a matrix of elements which relate said variables to each other onto a parallel processor which includes a plurality of processing cells, each cell having a memory, the matrix being comprised of a series of one dimensional arrays of said elements along orthogonal axes, the method comprising the steps of: transposing elements of each array along one axis of said matrix into a transpose vector, one transpose vector being transposed from each array along said one axis, each said transpose vector comprising values corresponding to said elements stored in a plurality of said cells, diagonal elements of said matrix being stored in a designated one of said cells; and generating an index for storage in association with each stored element of said vectors, said index being operative to identify the array along said second axis from which said stored element originates.

Claim 32

In a process for analyzing a physical system which can be defined by certain physical variables capable of being expressed in terms of a plurality of linear equations solvable by matrix manipulation methods, a machine implemented method for loading and storing a matrix of elements which relate said variables to each other onto a parallel processor which includes a plurality of processing cells, each cell having a memory, the matrix being comprised of a series of one dimensional arrays of said elements along orthogonal axes, the method comprising the steps of: transposing elements of each array along one axis of said matrix into a transpose vector, one transpose vector being transposed from each array along said one axis, each said transpose vector comprising values corresponding to said elements stored in a plurality of said cells, diagonal elements of said matrix being stored in a designated one of said cells; and generating an index for storage in association with each stored element of said vectors, said index being operative to identify the array along said second axis from which said stored element originates.

Claim 33

The method of claim 27 wherein said matrix is sparse and only computationally significant elements thereof are transposed into said transpose vectors.

Claim 34

The method of claim 28 wherein only non-zero elements are transposed.

Claim 35

The method of claim 29 further including the step of: processing said intermediate results from a plurality of processing cells as a function of said index.

Claim 36

The method of claim 27 wherein said step of transposing comprises scanning consecutive elements of said arrays.

Claim 37

The method of claim 27 including the further steps of concurrently operating on said stored non-diagonal elements with a plurality of previously determined operands to generate intermediate results in each cell; and storing said intermediate results in said cell based on said index.