We develop a direct finite-element solver of linear (optimal) complexity to extract broadband circuit parameters such as S-parameters of arbitrarily shaped 3-D interconnects in inhomogeneous dielectrics. Numerical experiments demonstrate a clear advantage of the proposed solver as compared with existing finite-element solvers that employ state-of-the-art direct sparse matrix solutions. A linear complexity in both CPU time and memory consumption is achieved with prescribed accuracy satisfied. A finite-element matrix from the analysis of a large-scale 3-D circuit in multiple dielectrics having 5.643 million unknowns is directly factorized in less than 2 hours on a single core running at 2.8 GHz.