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

在物理学、工程学和经济学的许多应用中，非局部算子被用来模拟相应的现象。这种运算符的特征在于，当运算符应用于数据集时，每个输出数据依赖于每个输入数据。例子有边界积分法中的积分算子、高斯变换、量子微扰论中的李普曼-施温格方程、非整数幂和微分算子的逆。在风险管理中建模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.