Factorization-in-Loop: Proximal Fill-in Minimization for Sparse Matrix Reordering

• URL: http://arxiv.org/abs/2511.09093v1
• Date: Thu, 13 Nov 2025 01:31:22 GMT
• Title: Factorization-in-Loop: Proximal Fill-in Minimization for Sparse Matrix Reordering
• Authors: Ziwei Li, Shuzi Niu, Tao Yuan, Huiyuan Li, Wenjia Wu,
• Abstract summary: We learn a reordering network by minimizing triangular factors of the reordered matrix to approximate the exact number of fill-ins.<n>For gradient based optimization, there is a large gap between the predicted node scores and resultant triangular factors in the optimization objective.<n> Experimental results on benchmark sparse matrix collection SuiteSparse show the fill-in number and LU factorization time reduction of our proposed method is 20% and 17.8% compared with state-of-the-art baselines.
• Score: 9.46982964997944
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fill-ins are new nonzero elements in the summation of the upper and lower triangular factors generated during LU factorization. For large sparse matrices, they will increase the memory usage and computational time, and be reduced through proper row or column arrangement, namely matrix reordering. Finding a row or column permutation with the minimal fill-ins is NP-hard, and surrogate objectives are designed to derive fill-in reduction permutations or learn a reordering function. However, there is no theoretical guarantee between the golden criterion and these surrogate objectives. Here we propose to learn a reordering network by minimizing \(l_1\) norm of triangular factors of the reordered matrix to approximate the exact number of fill-ins. The reordering network utilizes a graph encoder to predict row or column node scores. For inference, it is easy and fast to derive the permutation from sorting algorithms for matrices. For gradient based optimization, there is a large gap between the predicted node scores and resultant triangular factors in the optimization objective. To bridge the gap, we first design two reparameterization techniques to obtain the permutation matrix from node scores. The matrix is reordered by multiplying the permutation matrix. Then we introduce the factorization process into the objective function to arrive at target triangular factors. The overall objective function is optimized with the alternating direction method of multipliers and proximal gradient descent. Experimental results on benchmark sparse matrix collection SuiteSparse show the fill-in number and LU factorization time reduction of our proposed method is 20% and 17.8% compared with state-of-the-art baselines.

Related papers

• Diff-PCR: Diffusion-Based Correspondence Searching in Doubly Stochastic Matrix Space for Point Cloud Registration [0.8287206589886881]
  State-of-the-art methods have employed RAFT-like iterative updates to refine the solution.<n>We propose a novel approach that exploits the Denoising Diffusion Model to predict a searching for the optimal matching matrix.<n>Our method offers flexibility by allowing the search to start from any initial matching matrix provided by the online backbone or white noise.
  arXiv  Detail & Related papers  (2023-12-31T09:24:28Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms [9.245687221460654]
  Motivated by applications in single-cell biology and metagenomics, we investigate the problem of matrixing based on a noisy monotone Toeplitz matrix model. We establish fundamental statistical limit for this problem in a decision-theoretic framework and demonstrate that a constrained least squares rate. To address this, we propose a novel-time adaptive sorting algorithm with guaranteed performance improvement.
  arXiv  Detail & Related papers  (2022-01-17T14:53:52Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  In this paper, we propose to approximate a large square matrix with a product of sparse full-rank matrices. In the approximation, our method needs only $N(log N)2$ non-zero numbers for an $Ntimes N$ full matrix. We show that our method gives a better approximation when the approximated matrix is sparse and high-rank.
  arXiv  Detail & Related papers  (2021-09-16T18:42:21Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Learning the Positions in CountSketch [51.15935547615698]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work we propose the first learning algorithm that also optimize the locations of the non-zero entries. We show this algorithm gives better accuracy for low rank approximation than previous work, and apply it to other problems such as $k$-means clustering for the first time.
  arXiv  Detail & Related papers  (2020-07-20T05:06:29Z)
• Fast Rank Reduction for Non-negative Matrices via Mean Field Theory [5.634825161148483]
  We formulate rank reduction as a mean-field approximation by modeling matrices via a log-linear model on structured sample space. We empirically show that our rank reduction method is faster than NMF and its popular variant, lraNMF, while achieving competitive low rank approximation error on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2020-06-09T14:55:47Z)
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries [4.230158563771147]
  We present a new, simple and computationally efficient iterative method for low rank matrix completion. Our algorithm, denoted R2RILS for rank $2r$ iterative least squares, has low memory requirements.
  arXiv  Detail & Related papers  (2020-02-05T16:20:58Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.