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

orthogonal decompositionHermitian formpolynomial-time algorithmbilinear formGram-Schmidt methodparallel NC algorithm

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Pivoting techniques for symmetric Gaussian elimination

Cited in

(11)

• Testing isomorphism of graded algebras
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
• Computing isometry groups of Hermitian maps
• Optimal algorithms for linear problems with Gaussian measures
• scientific article; zbMATH DE number 4005454 (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
• The Gram-Schmidt algorithm for a general angle
• An Algorithm to Improve Nearly Orthonormal Sets of Vectors on a Vector Processor
• A fast isomorphism test for groups whose Lie algebra has genus 2
• Iterative algorithms for Gram-Schmidt orthogonalization
• scientific article; zbMATH DE number 3974171 (Why is no real title available?)

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)