Fast Computation of Cuts With Reduced Support by Solving Maximum Circulation Problems

We present a technique to efficiently compute optimal cuts required to solve 3-D eddy current problems by magnetic scalar potential formulations. By optimal cuts, we mean the representatives of (co)homology generators with minimum support among the ones with a prescribed boundary. In this paper, we obtain them by starting from the minimal (co)homology generators of the combinatorial two-manifold representing the interface between conducting and insulating regions. Optimal generators are useful because they reduce the fill-in of the sparse matrix and ease human-guided basis selection. In addition, provided that the mesh is refined enough to allow it, they are not self-intersecting. The proposed technique is based on a novel graph-theoretic algorithm to solve a maximum circulation network flow problem in unweighted graphs that typically runs in linear time.