| Interest in the numerical solution of the Laplace equation on regions with fractal boundaries arises both in mathematics and physics. In mathematics, examples include harmonic measure of fractals, complex iteration theory, and potential theory. In physics, examples include Brownian motion, crystallization, electrodeposition, viscous fingering, and diffusion-limited aggregation. In a typical application, the numerical simulation has to be on a very large scale involving at least tens of thousands of equations with as many unknowns, in order to obtain any meaningful results. Attempts to use conventional techniques have encountered insurmountable difficulties, due to excessive CPU time requirements of the computations involved. Indeed, conventional direct algorithms for the solution of linear systems require order O({dollar}Nsp3{dollar}) operations for the solution of an N {dollar}times{dollar} N- problem, while classical iterative methods require order O({dollar}Nsp2{dollar}) operations, with the constant strongly dependent on the problem in question. In either case, the computational expense is prohibitive for large-scale problems. We present a direct algorithm for the solution of the Laplace equation on regions with fractal boundaries. The algorithm requires O(N) operations with a constant dependent only on the geometry of the fractal boundaries. The performance of the algorithm is demonstrated by numerical examples, and applications and generalizations of the scheme are discussed. |
