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.