GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding

• URL: http://arxiv.org/abs/2607.27042v1
• Date: Wed, 29 Jul 2026 15:34:00 GMT
• Title: GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding
• Abstract summary: GPTQ, or equivalently Babai's nearest plane algorithm, rounds a real matrix to integers under a quadratic metric.<n>We present GPTQ-2D, which produces the identical rounded matrix in cubic time.
• Score: 54.10836630612739
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Adaptive rounding methods such as GPTQ, or equivalently Babai's nearest plane algorithm, round a real matrix to integers under a quadratic metric. They process the entries in a fixed order, one at a time, propagating each rounding error to the entries not yet processed through a triangular feedback matrix. We study the two-sided version of this task, in which fixed nonsingular basis matrices act on both the left and the right of the residual; the familiar one-sided case is the special case of an identity right basis. Vectorizing the matrix turns the two-sided objective into a quadratic metric whose Gram matrix is a Kronecker product, so the one-dimensional algorithm applies verbatim, but takes quartic time in the matrix dimension. We present GPTQ-2D, which produces the identical rounded matrix in cubic time. It rounds the entries anti-diagonal by anti-diagonal; entries on the same anti-diagonal are independent and are rounded in parallel.

Related papers

• New Insights into Involutory and Orthogonal MDS Matrices [1.9947454698470526]
  MDS matrices play a critical role in the design of diffusion layers for block ciphers and hash functions.<n>We show nontrivial interconnections between semi-involutory and involutory matrices.<n>We present explicit formulas for counting $3 times 3$ semi-involutory MDS matrices and semi-orthogonal MDS matrices.
  arXiv  Detail & Related papers  (2025-10-07T10:35:20Z)
• A note on MDS Property of Circulant Matrices [3.069335774032178]
  In $2014$, Gupta and Ray proved that the circulant involutory matrices over the finite field $mathbbF_2m$ can not be maximum distance separable (MDS) This article delves into circulant matrices possessing these characteristics over the finite field $mathbbF_2m$.
  arXiv  Detail & Related papers  (2024-06-22T16:00:00Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• Low-Rank Updates of Matrix Square Roots [7.832944895330117]
  We consider the matrix square root and inverse square root operations. Given a low rank perturbation to a matrix, we argue that a low-rank approximate correction to the (inverse) square root exists. We then discuss how a low-rank solution to that equation can be computed.
  arXiv  Detail & Related papers  (2022-01-31T12:05:33Z)
• Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
  We propose two more efficient variants to compute the differentiable matrix square root and the inverse square root. For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP), and the other method is to use Matrix Pad'e Approximants (MPA) A series of numerical tests show that both methods yield considerable speed-up compared with the SVD or the NS iteration.
  arXiv  Detail & Related papers  (2022-01-29T10:00:35Z)
• Fast Differentiable Matrix Square Root [65.67315418971688]
  We propose two more efficient variants to compute the differentiable matrix square root. For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP) The other method is to use Matrix Pad'e Approximants (MPA)
  arXiv  Detail & Related papers  (2022-01-21T12:18:06Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Simultaneous Block Diagonalization of Matrices of Finite Order [0.0]
  It is well known that a set of non-defect matrices can be simultaneously diagonalized if and only if the matrices commute. Here we give an efficient algorithm to explicitly compute a transfer matrix which realizes the simultaneous block diagonalization. Our main motivation lies in particle physics, where the resulting transfer matrix must be known explicitly in order to unequivocally determine the action of outer automorphisms.
  arXiv  Detail & Related papers  (2020-12-28T19:00:06Z)
• Periodicity of lively quantum walks on cycles with generalized Grover coin [0.17205106391379021]
  We extend the study of three state lively quantum walks on cycles by considering the coin operator as a linear sum of permutation matrices. We establish that an orthogonal matrix of order $3times 3$ is a linear sum of permutation matrices if and only if it is permutative.
  arXiv  Detail & Related papers  (2020-03-29T06:32:21Z)
• 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.