• Home
• Science
• Study
• Colloquium
• Events
• Contact
• Visitor
• Internal

Oberseminar
 

• Current Talks
• Preview
• Archive

Martin J. Gander

Universität Genf

An Algorithm with Optimal Complexity for Non-Matching Grid Projections

Abstract:

Non-matching grids are becoming more and more common in scientific computing. Two particular examples are the mortar methods in domain decomposition by Bernardi, Maday and Patera, and the patch method for local refinement by Glowinski, He, Lozinski, Rappaz and Wagner, which is also known under the name 'numerical zoom'. The former method permits an entirely parallel grid generation, where naturally the processor that will be computing approximations to the solution on a subdomain is also generating the grid for that subdomain, without communication. In the patch method, one has a large scale solver for a particular partial differential equation, and wants to add more precision in certain areas, without having to change the large scale code. One thus introduces refined patches in these regions with non-matching local grids, and uses a residual correction iteration between solutions on the patches and solutions on the entire domain, to converge to a more refined solution in the patch regions. In both examples, an essential step in the algorithm is the projection of a finite element function from one grid onto the finite element space of the other, non-matching grid. There are two problems that need to be addressed in order to obtain an efficient projection algorithm, a combinatorial one and a numerical one: the combinatorial one stems from the fact that in principle, every element of one grid could be intersecting with every element of the other grid, and hence the naive approach would immediately lead to an O(n^2) algorithm, where n is the number of elements. The numerical difficulty is related to the calculation of the intersection of two finite elements: which is numerically difficult, because one needs to take numerical decisions whether two lines intersect or not, and whether one point is in an element or not. I will describe an optimal complexity algorithm which overcomes both the combinatorial and numerical problems. It uses an advancing front technique and neighboring element information in order to reduce the combinatorial complexity to O(n) where n is the number of elements, independent of the dimension of the problem. The numerical problems for calculating the intersections are overcome by an inclusive strategy, which turns out to be numerically robust. I will show numerical experiments in two and three dimensions to illustrate the algorithm, and also show scaling experiments which confirm the optimal complexity of this new algorithm.