Optimal algorithms of Gram-Schmidt type

DOI10.1016/J.LAA.2013.02.026zbMATH Open1281.65067arXiv0910.0435OpenAlexW2079460463MaRDI QIDQ393367FDOQ393367

Authors: James B. Wilson 

Publication date: 17 January 2014

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

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.

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

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

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)

Cites Work

• Gaussian elimination is not optimal
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pivoting techniques for symmetric Gaussian elimination
• Finding central decompositions of \(p\)-groups.
• A generalization of the fast LUP matrix decomposition algorithm and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing isometry groups of Hermitian maps
• Constructing Maximal Subgroups of Classical Groups

Cited In (11)

• Computing isometry groups of Hermitian maps
• The Gram-Schmidt algorithm for a general angle
• Iterative algorithms for Gram-Schmidt orthogonalization
• Testing isomorphism of graded algebras
• Optimal algorithms for linear problems with Gaussian measures
• An Algorithm to Improve Nearly Orthonormal Sets of Vectors on a Vector Processor
• Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing
• A fast isomorphism test for groups whose Lie algebra has genus 2
• Title not available (Why is that?)
• Title not available (Why is that?)
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces

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)