Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction

DOI10.1090/S0025-5718-2012-02545-2zbMath1260.11082MaRDI QIDQ2894516

Xiao-Wen Chang, Damien Stehlé, Gilles Villard

Publication date: 29 June 2012

Published in: Mathematics of Computation (Search for Journal in Brave)

zbMATH Keywords

perturbation analysisQR factorizationlattice reductionLLL

Mathematics Subject Classification ID

Factorization of matrices (15A23) Number-theoretic algorithms; complexity (11Y16) Numerical computation of matrix norms, conditioning, scaling (65F35) Lattices and convex bodies (number-theoretic aspects) (11H06) Orthogonalization in numerical linear algebra (65F25)

Related Items (9)

Constructing totally p-adic numbers of small height ⋮ Perturbation analysis for the symplectic QR factorization ⋮ Fast practical lattice reduction through iterated compression ⋮ On the computation of the HNF of a module over the ring of integers of a number field ⋮ Perturbation analysis for the hyperbolic QR factorization ⋮ Improved rigorous perturbation bounds for the LU and QR factorizations ⋮ New rigorous perturbation bounds for the Cholesky-like factorization of skew-symmetric matrix ⋮ Mixed and componentwise condition numbers for matrix decompositions ⋮ On the quantum complexity of the continuous hidden subgroup problem

Uses Software

• mctoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The LLL algorithm. Survey and applications
• Factoring polynomials with rational coefficients
• Fast LLL-type lattice reduction
• Fast multiplication of large numbers
• Fast computation of continued fraction expansions.
• H-LLL
• Rigorous Perturbation Bounds of Some Matrix Factorizations
• A Componentwise Perturbation Analysis of the $QR$ Decomposition
• An LLL Algorithm with Quadratic Complexity
• Maximum likelihood sequence estimation from the lattice viewpoint
• Perturbation Analyses for the QR Factorization
• A more efficient algorithm for lattice basis reduction
• Accuracy and Stability of Numerical Algorithms
• Floating-Point LLL Revisited
• An LLL-reduction algorithm with quasi-linear time complexity
• Componentwise perturbation analyses for the QR factorization

This page was built for publication: Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction