Method and apparatuses for solving weighted planar graphs
AssigneeCarnegie Mellon University
InventorsGary Lee Miller, Ioannis Koutis
Life of this patent
Estimating the term…
Abstract
Methods and apparatuses for constructing a multi-level solver, comprising decomposing a graph into a plurality of pieces, wherein each of the pieces has a plurality of edges and a plurality of interface nodes, and wherein the interface nodes in the graph are fewer in number than the edges in the graph; producing a local preconditioner for each of the pieces; and aggregating the local preconditioners to form a global preconditioner.
Claims14
A method for constructing a multi-level solver for a linear system, the method comprising the steps of:
- a. providing a processor to execute the following steps of the method;
- b. decomposing a planar graph A of the linear system into a plurality of pieces, wherein each of the pieces has a plurality of edges and a plurality of interface nodes that are fewer in number than the edges;
- c. producing a local preconditioner for each of the pieces of the planar graph A;
- d. producing a planar global preconditioner graph B of the planar graph A by aggregating the local preconditioners;
- e. generating a planar graph C based on the planar global preconditioner B of the planar graph A, wherein the planar graph C is smaller than the planar graph A;
- f. substituting the planar graph A with the planar graph C;
- g. iterating between steps b-f until the planar graph C reaches a predetermined size to generate a sequence of graph A, global preconditioner graph B, and graph C to form a preconditioning hierarchy, wherein the planar graph A has an iteration count, wherein the global preconditioner graph B has an iteration count, wherein the iteration count of the planar graph A is the same as the iteration count of the global preconditioner graph B, wherein the planar graph C is smaller than the planar graph A, wherein the planar graph C has an iteration count;
- and
- h. applying the preconditioning hierarchy to a recursive preconditioned iterative method to solve the linear system.
A method for constructing a multi-level solver for a linear system, the method comprising the steps of:
- a. providing a processor to execute the following steps of the method;
- b. providing a planar graph A of the system, wherein the planar graph A has an iteration count;
- c. decomposing the planar graph A into a plurality of subgraphs;
- d. producing a planar graph B for each of the plurality of subgraphs, wherein the planar graph B has an iteration count, wherein the iteration count of the planar graph A is the same as the iteration count of the planar graph B;
- e. aggregating the planar graphs B of the plurality of subgraphs to form a global planar graph B;
- f. generating a planar graph C based on the global planar graph B, wherein the planar graph C is smaller than the planar graph A, wherein the planar graph C has an iteration count,
- g. forming a next planar graph A, wherein the next planar graph A is one iteration count higher than the iteration count of the planar graph A;
- h. equating the next planar graph A to the planar graph C;
- i. repeating steps c-h substituting the next planar graph A of step h for the planar graph A of step b until the planar graph C reaches a determined size;
- j. forming a hierarchy of paired planar graphs A and B, wherein a paired planar graph A is paired with a paired planar graph B of a lower iteration count than the paired planar graph A;
- and
- k. applying the hierarchy of paired planar graphs A and B to a recursive preconditioned iterative solver to solve the linear system.
Dependencies are inferred from the claim text.