Optimal algorithms of Gram-Schmidt type
Provides theoretically optimal algorithms for a fundamental linear algebra problem, but the practical impact is limited due to the abstract setting and lack of empirical validation.
The paper presents three Gram-Schmidt type algorithms for orthogonal decomposition of symmetric, alternating, or Hermitian forms over division rings, achieving optimal sequential complexity matching matrix multiplication and parallel NC complexity.
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.