An efficient methodology to calculate absolute permeability of porous media using a two-step algorithm is developed. In the first step, the creeping flow equations over the pore space are translated into a Darcy flow problem with the pore space being represented by appropriately chosen local flow conductivities. In the next step, a combined renormalization group and multi-level iterative Laplace solver approach is used to upscale the local conductivities to obtain the effective permeability for the full domain. The accuracy and computational efficiency of the proposed two-step local conductivity-Laplace scheme (LC-LAP) are tested against a FFT (fast Fourier transform) accelerated solver which uses a semi-implicit method for the pressure-linked equation (SIMPLE-FFT) and against a solver that features the GPGPU implementation of the multiple-relaxation-time lattice Boltzmann method (MRT-LBM). A detailed comparison is made by computing permeabilities from all three methods over model geometries and digitized images obtained from micron-scale-resolution computerized tomography (micro-CT) of sandstone rocks of varying porosities and heterogeneity levels. We observe an agreement between our method and either benchmark methods (SIMPLE-FFT and MRT-LBM) that is similar to the agreement between both benchmarks. On the samples tested, the computational performance advantage of the LC-LAP approach ranges from 10- to 40-fold compered to SIMPLE-FFT and 8- to 25-fold compared to MRT-LBM. The proposed method is suitable for fast computations and for computations over very large volumes (due to much lower memory and compute resource requirements) for determining single-phase permeabilities of medium- to high-permeability rocks.