Optimal algorithms of Gram-Schmidt type

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.

7 pages

References in corpus (1)

• Finding central decompositions of p-groups

Cited by in corpus (3)

• A fast isomorphism test for groups of genus 2
• Centralizers and conjugacy classes in finite classical groups
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions