Systems and methods for improved parallel ILU factorization in distributed sparse linear systems
AssigneeLandmark Graphics Corporation
InventorsQinghua Wang, James William Watts, III
Life of this patent
Estimating the term…
Abstract
Systems and methods for parallel incomplete LU (ILU) factorization in distributed sparse linear systems, which order nodes underlying the equations in the system(s) by dividing nodes into interior nodes and boundary nodes and assigning no more than three codes to distinguish the boundary nodes. Each code determines an ordering of the nodes, which in turn determines the order in which the equations will be factored and the solution performed.
Claims18
A method for ordering multiple nodes underlying equations in a distributed sparse linear system, comprising:
- designating nodes that do not have a connection that crosses a partitioning interface as interior nodes;
- designating nodes that have a connection that crosses a partitioning interface as boundary nodes;
- designating no more than three codes to distinguish the boundary nodes;
- processing each boundary node using a computer processor by:
- assigning a first code to each boundary node representing a first boundary node, wherein each first boundary node connection cannot cross a partitioning interface to connect two first boundary nodes;
- assigning a second code to each boundary node representing a second boundary node, wherein each second boundary node connection cannot cross a partitioning interface to connect two second boundary nodes;
- and
- assigning a third code to each boundary node representing a third boundary node, wherein each third boundary node connection cannot cross a partitioning interface to connect an interior node and each third boundary node connection can connect two third boundary nodes, a third boundary node and a second boundary node, or a third boundary node and a first boundary node.
A non-transitory program carrier device tangibly carrying computer executable instructions for ordering multiple nodes underlying equations in a distributed sparse linear system, the instructions being executable to implement:
- designating nodes that do not have a connection that crosses a partitioning interface as interior nodes;
- designating nodes that have a connection that crosses a partitioning interface as boundary nodes;
- designating no more than three codes to distinguish the boundary nodes;
- assigning a first code to each boundary node representing a first boundary node, wherein each first boundary node connection cannot cross a partitioning interface to connect two first boundary nodes;
- assigning a second code to each boundary node representing a second boundary node, wherein each second boundary node connection cannot cross a partitioning interface to connect two second boundary nodes;
- assigning a third code to each boundary node representing a third boundary node, wherein each third boundary node connection cannot cross a partitioning interface to connect nan interior node and each third boundary node connection can connect two third boundary nodes, a third boundary node and a second boundary node, or a third boundary node and a first boundary node.
Dependencies are inferred from the claim text.