Method and apparatus for pre-processing inputs to parallel architecture computers

Claim 3

The method of claim 1, wherein said permutation is defined by the steps of: (1) computing a set S={v|there is an edge (v,w) in E with deg G v<deg G w}; (2) computing connected components of an induced subgraph G(V-S); (3) classifying clique connected components of G(V-S); and (4) computing independent cliques in each nonclique connected component.

Claim 4

A pre-processor for automatic decomposition of a first problem belonging to a class of problems of a sparse, symmetric type into an equivalent suite of independent sub-problems, for allocation of each of said sub-problems to a computer in a network of parallel architecture computers, for concurrent operation of said computers to solve said sub-problems, and for arranging results of said concurrent operation into a solution of said first problem, comprising: means for generating a suite of signals from a sparsity structure of said first problem representing information content of a permutation of rows and columns of an externally input-matrix-vector pair defining said first problem; means for defining said suite of sub-problems comprising said first problem using said suite of signals to generate said permutation to define a block-bordered diagonal form leading to a sparse Schur-complement resolution, wherein said permutation is chosen such that every perfect parallelism in said class of problems corresponds to one of said sub-problems; means for allocating each of said sub-problems to one of said parallel architecture computers; means for directing said concurrent operation of said computers to solve said sub-problems; means for combining results of said concurrent operation into an arrangement for said sparse Schur-complement resolution; and means for output of said arrangement as a solution to said first problem.

Claim 5

A pre-processor for automatic decomposition of a first problem belonging to a class of problems of a sparse, symmetric type into an equivalent suite of independent sub-problems, for allocation of each of said sub-problems to a computer in a network of parallel architecture computers, for concurrent operation of said computers to solve said sub-problems, and for arranging results of said concurrent operation into a solution of said first problem, comprising: means for generating a suite of signals from a sparsity structure of said first problem representing information content of a permutation of rows and columns of an externally input-matrix-vector pair defining said first problem; means for defining said suite of sub-problems comprising said first problem using said suite of signals to generate said permutation to define a block-bordered diagonal form leading to a sparse Schur-complement resolution, wherein said permutation is chosen such that every perfect parallelism in said class of problems corresponds to one of said sub-problems; means for allocating each of said sub-problems to one of said parallel architecture computers; means for directing said concurrent operation of said computers to solve said sub-problems; means for combining results of said concurrent operation into an arrangement for said sparse Schur-complement resolution; and means for output of said arrangement as a solution to said first problem.

Claim 6

The pre-processor of claim 3, wherein said permutation is defined by the steps of: (1) computing a set S={v|there is an edge (v,w) in E with deg G v>deg G w}; (2) computing connected components of an induced subgraph G(V-S); (3) classifying clique connected components of F(V-S); and (4) computing independent cliques in each nonclique connected component.

Claim 7

The pre-processor of claim 4 wherein said pre-processor is operably coupled to a front-end computer in a network of parallel architecture computers comprising said front-end computer and a plurality of sub-processors operably connected to said front-end computer.