Optimal algorithms of Gram-Schmidt type

DOI10.1016/J.LAA.2013.02.026MaRDI QIDQ393367zbMATH OpenOpenAlexFDO

Authors James B. Wilson

Publication date 17 January 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.0435

zbMATH Keywords

bilinear formGram-Schmidt methodHermitian formorthogonal decompositionparallel NC algorithmpolynomial-time algorithm

Mathematics Subject Classification ID

Orthogonalization in numerical linear algebra (65F25) Parallel numerical computation (65Y05)

Abstract: Three algorithms of Gram-Schmidt type are given that produce an orthogonal decomposition of finite $d$-dimensional symmetric, alternating, or Hermitian forms over division rings. The first uses $d^3/3+O(d^2)$ ring operations with very simple implementation. Next, that algorithm is adapted in two new directions. One is an optimal sequential algorithm whose complexity matches the complexity of matrix multiplication. The other is a parallel NC algorithm with similar complexity.

Recommendations

• scientific article; zbMATH DE number 1439806
• scientific article; zbMATH DE number 4005454
• scientific article; zbMATH DE number 440657
• Iterative algorithms for Gram-Schmidt orthogonalization
• scientific article; zbMATH DE number 1254303

Cites work

• A generalization of the fast LUP matrix decomposition algorithm and applications
• Computing isometry groups of Hermitian maps
• Constructing Maximal Subgroups of Classical Groups
• Finding central decompositions of p-groups.
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 3778743 (Why is no real title available?)
• scientific article; zbMATH DE number 475366 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 1439806 (Why is no real title available?)
• scientific article; zbMATH DE number 3207297 (Why is no real title available?)
• Pivoting techniques for symmetric Gaussian elimination

Cited in

(13)

• Optimal algorithms for linear problems with Gaussian measures
• Iterative algorithms for Gram-Schmidt orthogonalization
• The Gram-Schmidt algorithm for a general angle
• scientific article; zbMATH DE number 3974171 (Why is no real title available?)
• scientific article; zbMATH DE number 4005454 (Why is no real title available?)
• An Algorithm to Improve Nearly Orthonormal Sets of Vectors on a Vector Processor
• scientific article; zbMATH DE number 1254303 (Why is no real title available?)
• Algorithms based on \(*\)-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
• A fast isomorphism test for groups whose Lie algebra has genus 2
• Testing isomorphism of graded algebras
• Computing isometry groups of Hermitian maps
• Extended Gram-Schmidt process on sesquilinear spaces over finite fields

This page was built for publication: Optimal algorithms of Gram-Schmidt type

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