用GPU快速计算矩阵核的整数基

Question

输入：具有整数项的n times m矩阵A。例如，考虑矩阵

A = [[2,1,0],[0,1,2]]

输出：A的内核/空空间的整数基础。例如，对于上述矩阵，整数基是

[[1,-2,1]]

我使用这篇stackoverflow文章中的想法，首先计算有理基，然后通过乘以分母的lcm来计算整数基，并使用以下(Python 2.7)代码：

import numpy as np
from sympy import Matrix,lcm
from fractions import Fraction
def ker_int_basis(B):
BKer = 1.0*np.array(Matrix(B).nullspace())
Bk =[]
for basis in BKer:
l = lcm(map(lambda x: Fraction(x).limit_denominator().denominator,map(str,basis)))
basis = map(int,l*basis)
Bk.append(basis)    
Bk = np.array(Bk)
return Bk

它适用于小例子。但上面的代码非常慢，而且我的矩阵是10000 times 500或更大。上面的代码即使运行了几个小时也不会输出。

如何使代码更快考虑到矩阵非常非常大，我更喜欢GPU实现。多核CPU也将是一种改进。甚至建议在上面的代码中更有效地使用循环和数据结构也是受欢迎的。

Answer 1

Sympy使用高斯消去法来计算B的零空间。这是$O(n^3)$，我认为这个计算是代码中的瓶颈(但值得检查)。

高斯消去可以通过同时进行所有消去来并行化。GE的算法相对简单，并且有许多浮点数的实现。然而，在我的简短搜索中，我没有看到其他符号包会使用有理数或整数来实现这一点(尽管你可能相对容易实现)。

为了在不重写算法的情况下使任务并行化，可以尝试的另一件事是将矩阵拆分为两组行，计算每一行的空空间，然后计算计算出的空空间的交集。如果每一组行都有相对较小的null空间，这会很好地工作，但如果它们都返回非常大的null空间就不那么好了。