Can someone provide an article or book that explains the principle used in frontal solvers? Some examples also may help understand the frontal methods better.Thanks in advance!


In my humble opinion, the most well-written paper for frontal method is:

Recently, many researchers tried embedding $H$- or $HSS$-matrix structures into the original multifrontal method to further reduce the complexity. For example, Superfast Multifrontal Method for Large Structured Linear Systems of Equations by Jianlin Xia, et al. In that paper he wrote, the complexity for 2D problem was $\mathcal{O}(n)$, and an $\mathcal{O}(n^{\frac{4}{3}})$ complexity for 3D problem, which is quite astonishing result.

  • $\begingroup$ You are overstating the result (which is not new) by shedding the problem-dependent parameter. The estimate is $\mathcal O(n p)$ (in 2D) where $p$ is a problem-dependent parameter quantifying the essential rank of vertex separators at the chosen error tolerance. If you take any fixed elliptic system and refine it, you always eventually get low rank structure. But multigrid could also get you that solution at the cost of the coarse level solve plus a handful of flops per fine mesh point. For multiscale problems (the kind where refinement matters), the rank is not constant under refinement. $\endgroup$ – Jed Brown Feb 29 '12 at 22:09
  • $\begingroup$ From a look at the results in Xia et al's paper, especially the selective reporting of results (like accuracy and convergence rates) and selection of only easy problems, it's clear that at this stage, the method does not actually work. $\endgroup$ – Jed Brown Feb 29 '12 at 22:42
  • $\begingroup$ @JedBrown Hi, thanks for the reply, actually the method works, in another paper by Lexing Ying and Phillip Schmitz: math.utexas.edu/users/lexing/publications/direct2d.pdf they tried this approach on FEM framework and it worked. $\endgroup$ – Shuhao Cao Mar 1 '12 at 1:14
  • $\begingroup$ I did not say that it couldn't work, I said that their implementation did not work. They only solve constant coefficient Poisson and elasticity. They need 44 CG iterations for the small elasticity problem and don't report how iterations scale for higher resolution. They need $10^5$ flops per degree of freedom for setup and don't report solve cost. Multigrid reliably solves these problems in a couple hundred flops. The Ying and Schmidtz paper uses a problem that doesn't actually make the problem difficult. At least they don't need an unspecified number of iterations... $\endgroup$ – Jed Brown Mar 1 '12 at 3:50
  • $\begingroup$ ... but if it worked, they would solve a hard problem with it. $\endgroup$ – Jed Brown Mar 1 '12 at 3:50

Irons, B. M., 1970. A frontal solution scheme for finite element analysis. Int. J. Numer. Methods Eng. 2, 5--32

Duff, I.S. , Erisman, A. M. , Reid, J.K. 1986. Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY

Davis, T. (2006). Direct Methods for Sparse Linear Systems. Fundamentals of Algorithms. SIAM, Philadelphia.

  • 1
    $\begingroup$ Paul, please give at least a little bit of commentary re: these sources. $\endgroup$ – Geoff Oxberry Feb 28 '12 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.