Computer Science – Numerical Analysis
Scientific paper
2011-10-20
Computer Science
Numerical Analysis
18 pages
Scientific paper
We define the notion of effective stiffness and show that it can used to build sparsifiers, algorithms that sparsify linear systems arising from finite-element discretizations of PDEs. In particular, we show that sampling $O(n\log n)$ elements according to probabilities derived from effective stiffnesses yields an high quality preconditioner that can be used to solve the linear system in a small number of iterations. Effective stiffness generalizes the notion of effective resistance, a key ingredient of recent progress in developing nearly linear symmetric diagonally dominant (SDD) linear solvers. Solving finite elements problems is of considerably more interest than the solution of SDD linear systems, since the finite element method is frequently used to numerically solve PDEs arising in scientific and engineering applications. Unlike SDD systems, which are relatively easy to precondition, there has been limited success in designing fast solvers for finite element systems, and previous algorithms usually target discretization of limited class of PDEs like scalar elliptic or 2D trusses. Our sparsifier is general; it applies to a wide range of finite-element discretizations. A sparsifier does not constitute a complete linear solver. To construct a solver, one needs additional components (e.g., an efficient elimination or multilevel scheme for the sparsified system). Still, sparsifiers have been a critical tools in efficient SDD solvers, and we believe that our sparsifier will become a key ingredient in future finite-element solvers.
Avron Haim
Toledo Sivan
No associations
LandOfFree
Effective Stiffness: Generalizing Effective Resistance Sampling to Finite Element Matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Effective Stiffness: Generalizing Effective Resistance Sampling to Finite Element Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Effective Stiffness: Generalizing Effective Resistance Sampling to Finite Element Matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-551118