Logotyp: till Uppsala universitets webbplats

Symmetry exploiting software based on the generalized Fourier transform (GFT) is presented from a practical design point of view. The algorithms and data structures map closely to the relevant mathematical abstractions, which primarily are based upon representation theory for groups. Particular care has been taken in the design of the data layout of the performance sensitive numerical data structures.

The use of a vanilla strategy is advocated for the design of flexible mathematical software libraries: An efficient general-purpose routine should be supplied, to obtain a practical and useful system, while the possibility to extend the library and replace the default routine with a special-purpose-even more optimized-routine should be supported.

Compared with a direct approach, the performance results show the superiority of the GFT based approach for so-called dense equivariant systems. The application is found to be well suited for parallelism.

We show that the generalized Fourier transform can be used for reducing the computational cost and memory requirements of radial basis function methods for multi-dimensional option pricing. We derive a general algorithm, including a transformation of the Black-Scholes equation into the heat equation, that can be used in any number of dimensions. Numerical experiments in two and three dimensions show that the gain is substantial even for small problem sizes. Furthermore, the gain increases with the number of dimensions.

Block-diagonalization of sparse equivariant discretization matrices is studied. Such matrices typically arise when partial differential equations that evolve in symmetric geometries are discretized via the finite element method or via finite differences.

By considering sparse equivariant matrices as equivariant graphs, we identify a condition for when block-diagonalization via a sparse variant of a generalized Fourier transform (GFT) becomes particularly simple and fast.

Characterizations for finite element triangulations of a symmetric domain are given, and formulas for assembling the block-diagonalized matrix directly are presented. It is emphasized that the GFT preserves symmetric (Hermitian) properties of an equivariant matrix.

By simulating the heat equation at the surface of a sphere discretized by an icosahedral grid, it is demonstrated that the block-diagonalization pays off. The gain is significant for a direct method, and modest for an iterative method.

A comparison with a block-diagonalization approach based upon the continuous formulation is made. It is argued that the sparse GFT method is an appropriate way to discretize the resulting continuous subsystems, since the spectrum and the symmetry are preserved.