  We present an asymptotically faster algorithm for solving linear systems in
well-structured 3-dimensional truss stiffness matrices. These linear systems
arise from linear elasticity problems, and can be viewed as extensions of graph
Laplacians into higher dimensions. Faster solvers for the 2-D variants of such
systems have been studied using generalizations of tools for solving graph
Laplacians [Daitch-Spielman CSC'07, Shklarski-Toledo SIMAX'08].
  Given a 3-dimensional truss over $n$ vertices which is formed from a union of
$k$ convex structures (tetrahedral meshes) with bounded aspect ratios, whose
individual tetrahedrons are also in some sense well-conditioned, our algorithm
solves a linear system in the associated stiffness matrix up to accuracy
$\epsilon$ in time $O(k^{1/3} n^{5/3} \log (1 / \epsilon))$. This
asymptotically improves the running time $O(n^2)$ by Nested Dissection for all
$k \ll n$.
  We also give a result that improves on Nested Dissection even when we allow
any aspect ratio for each of the $k$ convex structures (but we still require
well-conditioned individual tetrahedrons). In this regime, we improve on Nested
Dissection for $k \ll n^{1/44}$.
  The key idea of our algorithm is to combine nested dissection and support
theory. Both of these techniques for solving linear systems are well studied,
but usually separately. Our algorithm decomposes a 3-dimensional truss into
separate and balanced regions with small boundaries. We then bound the spectrum
of each such region separately, and utilize such bounds to obtain improved
algorithms by preconditioning with partial states of separator-based Gaussian
elimination.
