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

DOI10.1090/S0025-5718-2012-02545-2MaRDI QIDQ2894516zbMATH OpenFDO

Authors 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) Numerical computation of matrix norms, conditioning, scaling (65F35) Lattices and convex bodies (number-theoretic aspects) (11H06) Number-theoretic algorithms; complexity (11Y16) Orthogonalization in numerical linear algebra (65F25)

Recommendations

• scientific article; zbMATH DE number 5494062
• scientific article; zbMATH DE number 1852138
• An LLL algorithm with quadratic complexity
• Floating-Point LLL Revisited
• Adaptive precision floating point LLL

Cites work

• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 3859248 (Why is no real title available?)
• scientific article; zbMATH DE number 3980484 (Why is no real title available?)
• scientific article; zbMATH DE number 3440002 (Why is no real title available?)
• scientific article; zbMATH DE number 1852138 (Why is no real title available?)
• scientific article; zbMATH DE number 1852142 (Why is no real title available?)
• scientific article; zbMATH DE number 846277 (Why is no real title available?)
• scientific article; zbMATH DE number 5494062 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A Componentwise Perturbation Analysis of the $QR$ Decomposition
• A more efficient algorithm for lattice basis reduction
• Accuracy and Stability of Numerical Algorithms
• An LLL algorithm with quadratic complexity
• An LLL-reduction algorithm with quasi-linear time complexity, extended abstract
• Componentwise perturbation analyses for the QR factorization
• Factoring polynomials with rational coefficients
• Fast LLL-type lattice reduction
• Fast computation of continued fraction expansions.
• Fast multiplication of large numbers
• Floating-Point LLL Revisited
• H-LLL: using Householder inside LLL
• Maximum likelihood sequence estimation from the lattice viewpoint
• Perturbation Analyses for the QR Factorization
• Rigorous Perturbation Bounds of Some Matrix Factorizations
• The LLL algorithm. Survey and applications

Cited in

(10)

• Mixed and componentwise condition numbers for matrix decompositions
• On the quantum complexity of the continuous hidden subgroup problem
• New rigorous perturbation bounds for the Cholesky-like factorization of skew-symmetric matrix
• Improved rigorous perturbation bounds for the LU and QR factorizations.
• Fast practical lattice reduction through iterated compression
• scientific article; zbMATH DE number 5494062 (Why is no real title available?)
• Constructing totally \(p\)-adic numbers of small height
• 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
• Perturbation analysis for the symplectic QR factorization

Describes a project that uses

Uses Software

• mctoolbox

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2894516)