在我的图像处理算法实现中,我需要解决一个大型线性系统的形式为 A*x=b,其中:
- 矩阵 A=L+D 由拉普拉斯矩阵 L 和对角矩阵 D 相加得到 - 拉普拉斯矩阵 L 是稀疏的,每行大约有25个非零元素 - 这个系统很大,未知量与输入图像中的像素数量相同(通常>100万)
拉普拉斯矩阵 L 在算法的连续运行之间不会改变;我可以在预处理中构建这个矩阵,并可能计算其分解。对角矩阵 D 和右侧向量 b 在每次运行算法时都会改变。
我想找出在运行时解决此问题的最快方法;我不介意在预处理上花费时间(例如计算 L 的分解)。
我的初始想法是预先计算 L 的 Cholesky 分解,然后在运行时使用来自 D 的值更新分解(使用 cholupdate 进行秩1更新),并使用回代快速解决问题。不幸的是,Cholesky 分解不像原始的 L 矩阵那样稀疏,仅从磁盘加载就需要5.48秒;相比之下,使用 backslash 直接解决该系统需要8.30秒。
鉴于我的矩阵形状,您是否推荐任何其他方法来加速运行时的求解,无论预处理时间有多长?
- 矩阵 A=L+D 由拉普拉斯矩阵 L 和对角矩阵 D 相加得到 - 拉普拉斯矩阵 L 是稀疏的,每行大约有25个非零元素 - 这个系统很大,未知量与输入图像中的像素数量相同(通常>100万)
拉普拉斯矩阵 L 在算法的连续运行之间不会改变;我可以在预处理中构建这个矩阵,并可能计算其分解。对角矩阵 D 和右侧向量 b 在每次运行算法时都会改变。
我想找出在运行时解决此问题的最快方法;我不介意在预处理上花费时间(例如计算 L 的分解)。
我的初始想法是预先计算 L 的 Cholesky 分解,然后在运行时使用来自 D 的值更新分解(使用 cholupdate 进行秩1更新),并使用回代快速解决问题。不幸的是,Cholesky 分解不像原始的 L 矩阵那样稀疏,仅从磁盘加载就需要5.48秒;相比之下,使用 backslash 直接解决该系统需要8.30秒。
鉴于我的矩阵形状,您是否推荐任何其他方法来加速运行时的求解,无论预处理时间有多长?