The nested dissection method developed by Lipton, Rose, and Tarjan is a seminal method for quickly performing Gaussian elimination of symmetric real positive definite matrices whose support structure satisfies good separation properties (e.g. planar).One can use the resulting LU factorization to deduce various parameters of the matrix.The main results of this paper show that we can remove the three restrictionsof being ``symmetric'', being ``real'', and being ``positive definite'' and stillbe able to compute the rank and, when relevant, also the absolute determinant,while keeping the running time of nested dissection.Our results are based, in part, on an algorithm that, given an arbitrary square matrix $A$ of order $n$ having $m$ non-zero entries, creates another square matrix $B$ of order $n+2t=O(m)$ with the property that each row and each column of $B$ contains at most {em three} nonzero entries, and, furthermore, $rank(B)=rank(A)+2t$ and $det(B)=det(A)$. The running time of this algorithm is only $O(m)$, which is optimal.
展开▼
机译：由Lipton，Rose和Tarjan开发的嵌套解剖方法是一种用于快速执行支持结构满足良好分离特性（例如平面）的对称实际正面矩阵的最新方法.Ane可以使用所产生的LU分解来推导各种参数矩阵。本文的主要结果表明，我们可以删除“对称”“的三个限制，是”真实“，以及”正定的“，并无法计算等级，而且相关，也是绝对的决定因素，同时保持嵌套分析的运行时间。然后，部分地基于算法，给定任意平方矩阵$ N $ N $的任意方矩阵$ N $ ，使用每行和每一列的属性创建另一个方形矩阵$ n $ n + 2t = o（m）$，每行和每列$ b $包含大多数{em three}非零条目，而且，$等级（ b）=等级（a）+ 2t $和$ det（b）= det（a）$。此算法的运行时间仅为$ o（m）$，它是最佳的。
展开▼
