A fast LU factorization of linear complexity is developed to directly solve a dense system of linear equations for the capacitance extraction of any arbitrary shaped 3-D structure embedded in inhomogeneous materials. In addition, a higherorder scheme is developed to achieve any higher-order accuracy for the proposed fast solver without sacrificing its linear computational complexity. The proposed solver successfully factorizes dense matrices that involve more than one million unknowns in fast CPU run time and modest memory consumption. Comparisons with state-of-the-art integral-equation-based capacitance solvers have demonstrated its clear advantages.