The existence of nonlinear magnetic materials poses a challenge to the interconnect inductance extraction for circuits in micromotors, radio-frequency identification, and magnetoresistive random access memory. In this paper, we present a fast algorithm to extract inductance in the presence of nonlinear magnetic materials. The new algorithm models the nonlinear magnetic characteristics by solving the Landau-Lifshitz-Gilbert equation, and the nonhomogeneous magnetic characteristics by introducing a fictitious magnetic charge. To speed up the algorithm, we apply a number of innovative techniques, including the approximation of magnetic charge effect and the modeling of currents with solenoidal basis. Experimental results demonstrate the accuracy and efficiency of the new algorithm. Its relative error with respect to the commercial tool is below 3%, while its speed is up to one magnitude faster.