New types of adaptivity for the cross approximation of non-local operators

在物理、工程和经济的许多应用中，非局部算子被用来模拟各自的现象。这种运算符的特征在于，当运算符应用于数据集时，每个输出基准都依赖于每个输入基准。例如边界积分法中的积分算子、高斯变换、量子微扰理论中的Lippmann-Schwinger方程、非整数幂和微分算子的逆。在风险管理中建模Levy过程的积分算子也属于这一类。它们的离散化导致完全填充的矩阵，由于潜在的几何结构或所需的解的精度通常是大规模的。已经存储这样的矩阵可能是一个问题。然而，线性系统的数值解，其中它们表现为系数矩阵，目前不能在可接受的时间内完成。在本项目中，将开发和研究一种新的非局部算子的有效数值处理方法。快速多极方法和层次矩阵都可以用来处理具有对数线性复杂度的算子的大规模离散化。根据各自的方法，运算符以规定的精度局部近似或块近似。所得到的近似普遍适用于任何以系数矩阵形式出现的线性系统的右侧。如果要求解具有相同算子的许多系统，则这种近似特别有效。然而，通常（可能在大多数情况下）只有一个系统是为一个操作员解决的，因为它可能，例如，在模拟过程中发生变化。在这种情况下，不能利用近似的通用性。相反，这种普遍性是通过生成和存储可有可无的信息来实现的。由于目前替代方法很少，这种近似方法仍在实践中使用。这个项目的目的是通过开发一种新的技术来改善这种情况，这种技术可以调整右边的近似值。快速多极方法和层次矩阵都将受益于这种新方法。因此，成功和广泛认可的方法将被扩展到尚未有效应用的重大问题。

In many applications from physics, engineering and economy, non-local operators are used to model the respective phenomenon. Such operators are characterised by the property that each output datum depends on each input datum when the operator is applied to a data set. Examples are integral operators arising from the boundary integral method, the Gauss transform, the Lippmann-Schwinger equation in quantum perturbation theory, non-integer powers and the inverse of differential operators. Also integral operators for modelling Levy processes in risk management belong to this class. Their discretization leads to fully populated matrices which due to the underlying geometry or the desired accuracy of the solution are large scale in general. Already storing such matrices can be a problem. However, the numerical solution of linear systems in which they appear as a coefficient matrix can currently not be done in acceptable time.In this project a new approach for the efficient numerical treatment of non-local operators will be developed and investigated. Both, the fast multipole method and hierarchical matrices can be employed to treat large scale discretizations of such operators with logarithmic-linear complexity. Depending on the respective method, the operator is approximated locally or blockwisewith the prescribed accuracy. The resulting approximation is universally applicable to any right hand side of linear systems in which it appears as a coefficient matrix. If many systems with the same operator are to be solved, then this kind of approximation is particularly efficient. However, often (probably in most cases) only a single system is to be solved for one operator, because it may, for instance, change in the course of a simulation. In such a situation, the universality of the approximation cannot be taken advantage of. On the contrary, the universality is paid for by generating and storing dispensable information. Since there are currently few alternatives, this kind of approximation is still used in practise. The aim of this project is to improve this situation by developing a new technique which tailors the approximation to the right hand side. Both, fast multipole methods and hierarchical matrices will be able to benefit from this new approach. Hence, succesful and widely recognised methods will be extended to significant problems to which they have not been efficiently applicable yet.