高斯消元法-无需矩阵存储

Question

高斯消元法-无需矩阵存储

algorithmmatrix

3

我在执行高斯消元时遇到了问题。矩阵A非常大，而且无法根据我的内存限制进行存储，但是A的元素可以用i和j的函数来描述，即A(i,j) = f(i,j)。

此外，我不需要计算所有得到的上三角矩阵的元素。

现在的问题是，如何更新高斯消元算法，以使用f(i,j)来计算特定元素的结果矩阵，而不是计算所有元素？

更新：这是我的A矩阵：

                a_{11} & a_{12}  & a_{13}  & a_{14}  & .. & a_{1L} 
                q_1    & a_{22}  & a_{23}  & a_{23}  & .. & a_{2L} 
                q_2    & q_1     & a_{33}  & a_{34}  & .. & a_{3L} 
                q_3    & q_2     & q_1     & a_{44}  & .. & a_{3L} 
                q_4    & q_3     & q_2     & q_1     & .. & a_{3L} 
                 :     &  :      & :       & :       & :  & : 
                 :     &  :      & :       & :       & :  & : 
                q_L    & q_{L-1} & q_{L-2} & q_{L-3} & .. & a_{LL}

- user3842532

2

“我不需要计算结果上三角矩阵的所有元素”这句话是什么意思？我所知道的这个算法就需要计算所有元素。 - laune

1

@laune：“一个矩阵太大，你无法存储它？这是2014年！”可以想象要求一个在无限矩阵上运行的算法。然后输出将是一个返回指定条目结果的函数。当然，有一些无限矩阵可以计算其谱。 - Hooked

1

@laune：就像Hooked所说的，矩阵是无限的，但我有一个可以用来获取特定元素的函数。感谢你提醒我调整我的日历！ - user3842532

@Hamid，你使用的函数是什么来评估元素A(i,j)的？知道函数的周期也有助于减少内存和计算。 - Vikram Bhat

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AbcAeffchen · Answer 1

假设您想计算输入的 (m,n)。其中，m 表示行，n 表示列。

首先：如果 m > n，则该输入将为零，因为它在对角线下方。如果 m = n，则该输入将为一（该输入位于对角线上）。

因此，让 m < n。

我认为您可以通过仅存储 m^2+m 个输入来计算此输入：

保存第一行的前m个元素和第一个非零元素所在的第n列元素，将这些元素称为M_11,M_12,...,M_1m,M_1n。
将每个元素M_i除以M_1。
保存第一行的前m个元素和y中第n个元素，使得y_2 - y_1 * M_12不为零。
将该行保存为M_21,M_22,...M_2m,M_2n。
对于i = 2 ... m，执行M_2i = M_2i - M_1i * M_21。
对于下一行，查找对角线上有非零元素的行（在减去保存的行后）。

最终（经过m行计算），元素M_mn包含了你的结果。

注意：如果您需要交换两行，则必须保存新行的顺序。

关于空间和时间：
您可以利用空间换取一些时间，反之亦然。如果您不想保存m^2个条目，则可能仅需存储2m个条目，但这将花费大量时间，最多是m 的指数时间。

如果您了解有关 f（i，j）的更多信息，则可能有一种方法可以加快算法或减少所需的空间。