Search papers, labs, and topics across Lattice.
This paper introduces GPTQ-2D, an adaptive rounding method that efficiently rounds a real matrix to integers using a two-sided approach, significantly reducing computational complexity from quartic to cubic time. By leveraging the independence of entries on anti-diagonals, the method allows for parallel processing, which enhances performance without sacrificing accuracy. The results demonstrate that GPTQ-2D achieves the same rounded matrix as existing methods while operating in a more scalable manner, making it suitable for larger matrices.
Rounding matrices can be done in cubic time without losing accuracy, revolutionizing efficiency in computational tasks.
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.
