SDC based on discontinuous collocation and associated embedded schemes

[tlunet]

🏷️ Proposal for a master / bachelor thesis

Collocation $Q$-generators currently implemented in qmat allow to generate various type of collocation methods, with different node distribution and quadrature types. As it produces dense $Q$ matrix, this is used as base method for Spectral Deferred Correction based time-stepping scheme Dutt, Greengard & Rokhlin 2000, that use a lower triangular preconditioner to solve the all-at-once problem, reducing the computational complexity to get to collocation accuracy (see tutorial on SDC).

Currently, the $Q$ matrices for collocation are built using a simple straightforward approach : consider the given (distinct) nodes, one simply build the Lagrange polynomial basis on those nodes, and integrate it on the intervals defined by the nodes to retrieve the $Q$ matrix (similar idea for the weights). However, this may not be the unique way to build a $Q$ matrix using a given set of nodes ...

🔍 In the literature, there is not one unique way to define $Q$ for LOBATTO based collocation method. For instance, with two Lobatto nodes, the $Q$ matrix produced by qmat is :

>>> from qmat.qcoeff.collocation import Collocation
>>> gen = Collocation(2, nodeType="LEGENDRE", quadType="LOBATTO")
>>> print(gen.Q)
[[0.  0. ]
 [0.5 0.5]] 

which corresponds according to the literature to a Lobatto IIIA method. However, there is a big familly of Lobatto methods (Lobatto IIIB, Lobatto IIIC, ...) that have the same nodes and weights, but different $Q$ matrix. Some approaches are called discontinuous collocation, and all are regrouped in the family of generalized Lobatto methods.

🔍 Similar considerations can be done for Radau-based methods ...

Furthermore, as it can be seen in the Wikipedia page, some embedded scheme can be built with some of the collocation methods : if we consider generic $Q$-coefficients :

$$ Q\text{-coefficients : } \begin{array}{c|c} \tau & Q \\ \hline & w^\top \end{array} $$

then we can obtain $w_2$ weights allowing to get a lower accuracy order from the same stage solution (usually one order less than the base method), used to create adaptive time-stepping methods.

The idea of this project is then as follow : investigate the discontinuous collocation methods in the literature, and find out if there is a generic way to compute different types of Q matrices for a given set of nodes. Then investigate the generation of embedded weights for this set of nodes, and finally apply the associated embedded methods on some classical ODE test problems.
Once it's done, then it would be again straightforward to investigate discontinuous collocation based SDC, in particular investigate time-parallel forms of SDC.

Proposed roadmap for this project :

1. Analyze general discontinuous collocation methods, to find out how they relate to each others.
2. Implement new $Q$-generators in qmat allowing to generate $Q$-coefficients for discontinuous collocation.
3. Investigate collocation and SDC-type time-stepping based on discontinuous collocation and their potential time-parallel SDC sweepers.
4. Apply those newly developed (time-parallel) schemes on given test problems (to be determined ...)

This can be subject to modifications before or during the project, and additional steps can eventually be added depending on the pace of the project.

Required :

• good knowledge in numerical method for scientific computing and ordinary differential equations
• good competences in Python programming
• intellectual curiosity and ability to independently search for information in the scientific literature

In case you are interested, please send a resume and brief motivation email to :

• thibaut.lunet@tuhh.de (@tlunet, TUHH, Hamburg, Germany)
• t.baumann@fz-juelich.de (@brownbaerchen, JSC, Jülich, Germany)