Algorithms for modeling compressible phenomena in multi-phase flows are developed. Timemarching preconditioned methodology is used as the algorithmic framework because of its inherent capability of handling multiple flow regimes, such as the incompressible bulk liquid flow, low Mach number compressible vapor flow and transonic/supersonic twophase mixture flow. Two formulations are obtained based upon whether the volume fraction or mass fraction forms of the phasic continuity equations are used in the derivation. Both preconditioning systems are observed to have identical eigenvalues, indicating that they should both perform well in practice. Computational results of simple test problems and practical engineering applications are presented to verify the capabilities of the formulation.