Methods and systems for using bi-directional level sets to partition an undirected graph representing a matrix to be used in cae

Abstract

An N×N matrix is generated from computerized model representing a physical domain, comprises coefficients of N simultaneous linear equations with N unknown physical quantities associated with N degrees-of-freedom of the physical domain, and is represented by an undirected graph having N vertices connected by a plurality of edges. A best suitable partition scheme for dividing the N vertices into a separator group and, first and second mutually independent groups as follows: distance vectors of source vertices selected from the N vertices are calculated; for each distinct pair of the source vertices, the difference of respective distance vectors is used for finding a coarse graph whose adjacency coarse matrix is pentadiagonal; a trial partition scheme is determined using the coarse graph initially; the separator group is then iteratively improved by trimming vertices contained therein and merging them into one of the mutually independent groups until the separator group becomes minimal.