Loading...
Please wait, while we are loading the content...
Similar Documents
Variable order panel clustering (extended version)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Sauter, Stefan A. |
| Copyright Year | 1999 |
| Abstract | We present a new version of the panel clustering method for a sparse rep resentation of boundary integral equations Instead of applying the algorithm separately for each matrix row as in the classical version of the algorithm we employ more general block partitionings Furthermore a variable order of approximation is used depending on the size of blocks We apply this algorithm to a second kind Fredholm integral equation and show that the complexity of the method only depends linearly on the number say n of unknowns The complexity of the classical matrix oriented approach is O n while for the classical panel clustering algorithm it is O n log n Introduction Elliptic boundary value problems with constant coe cients can be transformed into integral equations on the boundary of the domain via the method of integral equa tions From the numerical point of view this approach is interesting especially for problems on unbounded domains where the direct discretization with nite element or nite di erences is not straightforward Boundary integral equations are discretised in many engineering applications via the boundary element method by lifting conventional nite element spaces onto the surface of the domain Due to the non localness of the integral operators the arising system of equations is fully populated Hence the work for the classical matrix oriented approach grows quadratically in the number n of unknowns In and the panel clustering algorithm was introduced for collocation methods By using polynomial approximations of the kernel function of the integral operator it was possible to split the dependence of the integration variable from the source points The algorithm was applied for each matrix row separately In it was shown that the complexity of the algorithm is proportionally to O n log n with moderate In the panel clustering algorithm was introduced for the Galerkin discretization of boundary integral equations The key role plays a symmetric factorization of the kernel function with respect to both variables Again the algorithm is applied to each matrix row separately In the fast multipole method was introduced for the e cient eval uation of sums in multiple particle systems Here the algorithm was applied not pointwise but appropriate block partitionings are employed The complexity of the algorithm is again proportionally to O n log n In a block version of the panel clustering algorithm was introduced The complexity is still O n log n while the constants in the complexity estimates are smaller than for the classical approach In our paper we introduce a variable order approximation on the clusters resulting in an algorithm with complexity O n As a model problem we consider a Galerkin discretization of a second kind Fredholm integral equation The fact that boundary integral equations can be realized with full stability and consistency in O n oper ations whilst the classical matrix oriented approach has complexity O n seems to be of interest Generalizations of our approach to more general integral equations are the topic of future research Another way of a sparse approximation of boundary integral operators are wavelet discretizations In the past decade they were intensively developed for boundary integral equations There are versions for second kind integral equations by complexity O n log n The approach presented in reduces the complexity to O n However the e ciency of wavelet methods depends on the number of smooth charts being employed for the representation of the surface If the surface is rough and complicated the e ciency breaks down while the panel clustering method works especially well for complicated surfaces An algebraic approach to the data sparse realization of non local operators are H matrices see Matrix blocks are approximated by low rank matrices The choice of the approximation system can be based on a singular value decomposition and is suited to approximate inverses of sparse matrices e ciently In this paper various notations and conventions will be used In order to improve readability we have collected below the most relevant ones along with a link to their rst appearance |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.mis.mpg.de/preprints/1999/preprint1999_52.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
