  A butterfly-accelerated volume integral equation (VIE) solver is proposed for
fast and accurate electromagnetic (EM) analysis of scattering from
heterogeneous objects. The proposed solver leverages the hierarchical
off-diagonal butterfly (HOD-BF) scheme to construct the system matrix and
obtain its approximate inverse, used as a preconditioner. Complexity analysis
and numerical experiments validate the $O(N\log^2N)$ construction cost of the
HOD-BF-compressed system matrix and $O(N^{1.5}\log N)$ inversion cost for the
preconditioner, where $N$ is the number of unknowns in the high-frequency EM
scattering problem. For many practical scenarios, the proposed VIE solver
requires less memory and computational time to construct the system matrix and
obtain its approximate inverse compared to a $\mathcal{H}$ matrix-accelerated
VIE solver. The accuracy and efficiency of the proposed solver have been
demonstrated via its application to the EM analysis of large-scale canonical
and real-world structures comprising of broad permittivity values and involving
millions of unknowns.
