用深度学习联合优化稀疏矩阵重排与分解，减少填充项。
Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction
- 通过多尺度图神经网络学习矩阵的谱嵌入，捕捉全局结构。
- 在多个数据集上性能优于传统算法和现有深度学习方法。
- 适合需要高效稀疏计算的科学计算与工程仿真场景。
稀疏矩阵重排可显著减少矩阵分解过程中的填充项，从而降低计算与存储开销。寻找最小填充重排被证明是NP难问题。且存在悖论：重排在分解前进行，但重排目标——填充项却由分解生成。为弥合重排与分解间的鸿沟，我们提出一种基于谱嵌入的深度学习框架，以最小化填充项代理函数。首先，采用多尺度图神经网络架构，近似其图拉普拉斯矩阵的最小特征向量，即谱嵌入，捕获矩阵的全局结构信息；其次，使用另一多尺度图神经网络架构，基于秩分布最小化填充可能发生的势能空间。实验表明，该方法在多个数据集上表现与传统图论算法及深度学习方法相当甚至更优。
原文摘要 · Abstract (English)
Sparse matrix reordering can significantly reduce the fill-in during matrix factorization, thereby decreasing the computational and storage requirements in sparse matrix computations. Finding a minimal fill-in ordering is known to be an NP-hard problem. Moreover, there is a paradox: matrix reordering is applied before matrix factorization, but fill-ins that matrix reordering methods aim at are generated from matrix factorization. To bridge the gap between reordering and factorization, we propose a deep learning framework to minimize a fill-in surrogate function based on spectral embedding. First, we employ a multi-grid-like GNN architecture to learn to approximate the smallest eigenvectors of its graph Laplacian matrix, i.e. spectral embedding, and capture the global structural information of the matrix. Then, another multi-grid-like GNN architecture is used to minimize the potential space where fill-in can occur based on the rank distribution. Experimental results indicate that our approach achieves competitive performance compared with traditional graph-theoretic algorithms and deep learning methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。