A linear complexity direct matrix solution is developed for a full-wave-based impedance extraction of arbitrarily-shaped 3-D non-ideal conductors embedded in multiple dielectrics. It successfully overcomes the numerical challenge of directly solving a highly irregular system matrix that is mixed with both dense and sparse blocks. The proposed direct solver is shown to outperform state-of-the-art impedance solvers with fast CPU time, modest memory-consumption, and without sacrificing accuracy. The inverse of a 2.6-million-unknown matrix resulting from the impedance extraction of a large-scale 3-D interconnect having 128 buses, which is a matrix solution for 2.6 million right hand sides, was obtained in less than 1.5 GB memory and 1.3 hours on a single CPU running at 2.66 GHz.