在使用 numpy 的高斯消除实现中找不到瓶颈

Question

在我的数值方法中 class 上学期我在 c++ 中使用特征值实现了高斯消去法，并根据特征值中的内置方法对其进行了评分。我现在为我的同学们正在尝试将我所有的代码从 c++/eigen 翻译成 numpy，我也（错误地认为）对 numpy 和 python.

感觉更舒服

但是，下面这段代码慢了好几个数量级，以至于我确信我犯了一个错误。但它看起来与 C++ 代码一模一样。

我认为这可能是 row-major/column-major 排序问题，但这并没有改善任何东西。

如果有人能发现我的错误并指出导致这种超级减速的原因，我将不胜感激。

def gauss_elimination(A, b, show_steps = True):
#A = np.asfortranarray(A)
n = A.shape[0]
Ab = np.zeros((n, n+1))
Ab[:,:n] = Ab[:, :n] + A
Ab[:, n] = b
if (show_steps):
    print(Ab)
#turn the matrix into step form
for i in range(n-1):
    pivot = Ab[i,i] #select pivot
    for row in range(i + 1, n):
        factor = Ab[row, i] / pivot #get factor
        if (show_steps):
            print(f"Subtracting {factor} times the {i} row from the {row} row")
        Ab[row, i:] = Ab[row, i:] - Ab[i, i:] * factor #subtract factor times previous row 
        #from current row after pivot column
        time.sleep(0.5)
        if(show_steps):
            print(Ab)
        
#backsubstituion
if (Ab[n-1, n-1] == 0):
    print("0 Pivot")
Ab[n-1, n] = Ab[n-1, n] / Ab[n-1, n-1]
for i in range(n-1)[::-1]: #traverse from the bottom row up
    for k in range(i+1, n): #iterate over found solutions so far
        Ab[i, n] = Ab[i, n] - Ab[k, n] * Ab[i, k] #subtract the solution x[k] times Ab[i, k] from solution column
        if (Ab[i, i] == 0):
            print("Pivot = 0")
        Ab[i, n] = Ab[i, n]/ Ab[i, i] #normalize i.e. get a leading one on the diag
#save solution
x = Ab[:, n]
if (show_steps):
    print(f"Solution \n {x.transpose()}")
return x

谢谢！

Answer 1

如果您的 python 代码比 C++ 慢大约 100 倍，那没关系。您可以在网络上找到基准，了解 python 与 C++[1]

相比有多快

请注意，您的代码中有一个 time.sleep。对于 32x32.

，在 15 毫秒内删除您的函数运行s

您的代码在 python 级别具有 O(n^2) 复杂度，在 CPU 级别具有 O(n^3) 操作。如果您使用中等 n 进行测试，则 python 解释器开销将占主导地位。随着矩阵大小的增加，两次运行之间的差异开始变小。

在使用 numpy 的高斯消除实现中找不到瓶颈

Can't find bottleneck in Gaussian Elimination implementation using numpy

python

numpy

linear-algebra