Optimal Gram-Schmidt type algorithms. (arXiv:0910.0435v1 [math.NA])

A Gram-Schmidt type algorithm is given for finite $d$-dimensional reflexive
forms over division rings. The algorithm uses $d^3/3+O(d^2)$ ring operations.
Next, that algorithm is adapted in two new directions. First a sequential
algorithm is given whose complexity matches the complexity of matrix
multiplication. Second, a parallel NC algorithm is given with similar
complexity.

Published by

Original source : http://arxiv.org/abs/0910.0435...