Optimal algorithms of Gram-Schmidt type

James B. Wilson
Arxiv ID: 0910.0435Last updated: 11/23/2020
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.

PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.

Related papers

Commercial Disclosure
© 2023 Paper Studio™. All Rights Reserved.