解决方法A x = bAx=b对于带有更新的稀疏(带状)一种A

计算科学 线性代数 稀疏矩阵 scipy 带状矩阵 矩阵分解
2021-12-16 18:22:48

我想使用 Crank-Nicolson 方案求解与时间相关的薛定谔方程。我最终得到以下矩阵方程

A_fixed = ...  # the matrix that does the finite difference method
B_fixed = ...  # the matrix that does the finite difference method
A = A_fixed - diags(V)  # Add the potential term V to the diagonal of A_fixed
B = B_fixed + diags(V)  # Add the potential term V to the diagonal of A_fixed  

# solve for psi_new at each time step:
A.dot(psi_new) = B.dot(psi_old)   # psi_old is the solution at the previous time-step

是稀疏矩阵,所有项都沿主/非对角线(这称为“带状”吗?)。求解上述矩阵方程的最佳方法是什么?AB

我正在使用 scipy 库sp.sparse.linalg,它提供了solve一种使用 LU 分解的方法。如果潜在项与时间无关,那么实际上在整个计算过程中都是固定的,因此我可以使用它来预先分解这给了我 2 倍的速度。VABsp.sparse.linalg.factorizedA

但是如果是随时间变化的,那么在每个时间步都会发生变化怎么办?是否有适用于这个特定问题的算法(其中都由固定项和一些仅添加到主对角线的时变项组成)?VABAB

1个回答

的唯一非零条目中有,则带宽为 1 的带状矩阵。更一般地,您可以讨论带宽为的矩阵其中是任意整数。例如,如果您使用使用更多点来计算导数的高阶有限差分离散化,您将获得更高带宽的矩阵。Aijj{i1,i,i+1}Akk

时间内求解具有带状矩阵的系统是矩阵的大小;这本质上是托马斯算法由于您已经在使用 scipy,它有一个内置的带状矩阵求解器,尽管您可能必须更改将矩阵存储为带状格式的方式。带状求解器应该比一般的稀疏分解要快得多,因为它避免了存储矩阵的分解形式。O(bandwidth2n)n

就时变项而言,最好的办法是在每个时间步上调用更新矩阵上的带状求解器。如果您使用的是迭代方法,并且与时间无关项相比,时变项的幅度较小,那么使用迭代线性求解器可能会有一些优势。

虽然您的矩阵是带状的,但许多人在添加单位矩阵或对角矩阵的倍数后询问是否更新一般稀疏或密集矩阵的 LDU 分解。对于一般矩阵和全秩更新,如果您想利用过去求解的信息,您很不走运,需要使用迭代方法。