In this paper, the problem of real-time rendering of objects with all-frequency shadows is discussed. Current techniques are limited to memory inefficient, CPU consuming algorithms. In the approach proposed, a wavelet transform based pre-computed radiance transport (PRT) algorithm is used to generate the PRT matrix, which is encoded later into a sparse form that is easy to be utilized by the GPU. Rendering is performed by a fast, highly parallel relighting algorithm written in GPU fragment shader. The algorithm fully utilizes the parallelism nature of the GPU, and achieves one order increasing of the scene relighting speed compared with the current best CPU technique. In the same time, the runtime algorithm decreases the memory usage and gets a better load balance between the CPU and GPU.