Cache aware adaptive parallel multilevel implementations of the Finite Element Method using space trees and space filling curves

Adaptivity and multilevel approaches are usual in conflict with locality of memory access, causing bad performance on modern computer architectures. We show that the concept of Peano space filling curves based on arbitrarily refined space trees allow an implementation using essentially only stacks as data structures. The number of stacks does not depend on the number of unknowns or on the structure of refinement. Note that accesses to a stack cannot "jump" in the memory; they can move only to neighbouring memory locations, so the number of cache misses is usually very small. Moreover, the memory overhead for the definition of the domain and the refinement structure of the problem is negligible (a few bits for every degree of freedom).This allows the efficient solution of very large problems on relatively small parallel computers.