A scheme was devised to compute the pre-defined wavelet packet (PWP) basis functions and implement the preconditioning operation in the space domain. Numerical results show that the PWP preconditioner is effective in accelerating the convergence rate of iterative solution for deep cavity structures. Further, it is demonstrated that the total computational complexity and memory costs for the preconditioner can be kept to O(NlogN).