论文标题
快速迭代矩阵反转的高阶方法的概括适合GPU加速度
Generalization of Higher Order Methods for Fast Iterative Matrix Inversion Suitable for GPU Acceleration
论文作者
论文摘要
最近的技术发展导致了大数据处理，这在求解大规模的线性系统或反相矩阵时造成了严重的计算困难。结果，通过图形处理单元（GPU）加速度的快速近似迭代矩阵反转方法一直是一项广泛研究的主题，可以找到经典和直接反转的解决方案。当前使用的一些方法是Neumann Series（NS），Newton Iteration（NI），Chebyshev迭代（CI）和连续的过度释放，以引用一些。在这项工作中，我们根据NS开发了一种新的迭代算法，我们将其命名为“ Nested Neumann”（NN）。这种新方法可以通过利用对给定“构成深度”的函数的计算免费迭代更新来概括Ni（或CI）的较高订单。在数学上证明，NN：（i）鉴于预处理满足NS的光谱规范条件，（ii）的收敛速率已显示出等同于该顺序（Inception Plus Plus 1），并且（iii）具有最佳的启动深度深度，这是一个或Preppey prepertion prepthers devention prection prack ram，它具有最佳的深度。此外，考虑到计算成本的增加，我们得出了NN的明确公式，该公式适用于大量稀疏矩阵。重要的是，NN发现NS与NN（NI，CI和更高订单）之间的分析等效陈述，这对于MMIMO系统很重要。最后，NN方法适用于矩阵反转的阳性半明确矩阵，并且适用于任何线性系统（稀疏，非SPARSE，复杂等）。
Recent technological developments have led to big data processing, which resulted in significant computational difficulties when solving large-scale linear systems or inverting matrices. As a result, fast approximate iterative matrix inversion methodologies via Graphical Processing Unit (GPU) acceleration has been a subject of extensive research, to find solutions where classic and direct inversion are too expensive to conduct. Some currently used methods are Neumann Series (NS), Newton iteration (NI), Chebyshev Iteration (CI), and Successive Over-Relaxation, to cite a few. In this work, we develop a new iterative algorithm based off the NS, which we named 'Nested Neumann' (NN). This new methodology generalizes higher orders of the NI (or CI), by taking advantage of a computationally free iterative update of the preconditioning matrix as a function of a given 'inception depth'. It has been mathematically demonstrated that the NN: (i) convergences given the preconditioning satisfies the spectral norm condition of the NS, (ii) has an order of rate of convergence has been shown to be equivalent to the order (inception depth plus one), and (iii) has an optimal inception depth is an inception depth of one or preferably two, depending on RAM constraints. Furthermore, we derive an explicit formula for the NN, which is applicable to massive sparse matrices, given an increase in computational cost. Importantly, the NN finds an analytic equivalancy statement between the NS and the the NN (NI, CI, and higher orders), which is of importance for mMIMO systems. Finally, the NN method is applicable positive semi-definite matrices for matrix inversion, and applicable to any linear system (sparse, non-sparse, complex, etc.).
