A Fast Direct Algorithm for the Solution of the Laplace Equation on Regions with Fractal Boundaries
A Fast Direct Algorithm for the Solution of the Laplace Equation on Regions with Fractal Boundaries
复制标题
求解分形边界区域拉普拉斯方程的快速直接算法
DOI：
10.1006/jcph.1994.1116
复制
发表时间：
1994
影响因子：
4.1
通讯作者：
V. Rokhlin
中科院分区：
文献类型：
--
作者：
P. Jones;J. Ma;V. Rokhlin
本文提出了一种快速直接求解具有分形边界区域上的拉普拉斯方程的算法。在一个典型的应用中，数值模拟必须是非常大的规模，涉及至少数万个方程和尽可能多的未知数，以获得任何有意义的结果。由于所涉及的计算需要过多的CPU时间，使用传统技术的尝试遇到了难以克服的困难。实际上，求解线性系统的传统直接算法需要O（N3）阶运算来求解N-N问题，而经典迭代方法需要O（N2）阶运算，常数强烈依赖于所讨论的问题。在任何一种情况下，计算费用是禁止的大规模问题。本文的直接算法需要O（N）的操作与常数只依赖于边界的几何形状，使其更加实用的大规模的问题中遇到的分形，复杂的迭代理论，潜在的理论，和生长现象，如结晶，电沉积，粘性指，和扩散限制聚集的调和测度的计算。
An algorithm is presented for the rapid direct solution of the Laplace equation on regions with fractal boundaries. 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(N3) operations for the solution of an N � N-problem, while classical iterative methods require order O(N2) operations, with the constant strongly dependent on the problem in question. In either case, the computational expense is prohibitive for large-scale problems. The direct algorithm of the present paper requires O(N) operations with a constant dependent only on the geometry of the boundary, making it considerably more practical for large-scale problems encountered in the computation of harmonic measure of fractals, complex iteration theory, potential theory, and growth phenomena such as crystallization, electrodeposition, viscous fingering, and diffusion-limited aggregation.