<p>Suppose we are given $m$ vectors $v_1, \dots, v_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the subspace perpendicular to $v_1, \dots, v_m$. I could do this by Gram-Schmidt but this would appear to take roughly $(m+n)^3$ time in serial, and cannot be done at all in parallel. Maybe we can assume $m = O(n)$ if this simplifies things.</p>

<p>Are there better algorithms for this? This seems closely related to matrix inversion so one should expect algorithms running in time $n^{\omega}$ (serial) or NC algorithms in time $\log^2 n$ (in parallel). Any references or key words would be greatly appreciated.</p>

CC BY-SA 3.0
2014-08-01T16:11:31.757Z
It sounds like you want a QR factorization in $n^\omega$ time. From the matrix pseudoinverse (which I know for sure can be computed in $n^\omega$) you can get a projection matrix for the orthogonal complement of the span of $v_i$. There should be some easy way to get an orthonormal basis from that, but I am not quite seeing it.
Sasho Nikolov
CC BY-SA 3.0
2014-08-01T16:23:39.747Z
I think Schonhage's paper "Fast Schmidt orthogonalization and unitary transformations of large matrices" from 1973 answers your question. But I can't find it.
Sasho Nikolov
<ds.algorithms><linear-algebra><dc.parallel-comp>
Algorithm (parallel and serial) for Gram-Schmidt
David Harris
# Algorithm (parallel and serial) for Gram-Schmidt

(Asked by: username_0 on 2014-08-01)

Suppose we are given $m$ vectors $v\_1, \dots, v\_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the subspace perpendicular to $v\_1, \dots, v\_m$. I could do this by Gram-Schmidt but this would appear to take roughly $(m+n)^3$ time in serial, and cannot be done at all in parallel. Maybe we can assume $m = O(n)$ if this simplifies things.

Are there better algorithms for this? This seems closely related to matrix inversion so one should expect algorithms running in time $n^{\omega}$ (serial) or NC algorithms in time $\log^2 n$ (in parallel). Any references or key words would be greatly appreciated.

**Tags:** ds.algorithms, linear-algebra, dc.parallel-comp
> **Comments:**
> **username_1**: It sounds like you want a QR factorization in $n^\omega$ time. From the matrix pseudoinverse (which I know for sure can be computed in $n^\omega$) you can get a projection matrix for the orthogonal complement of the span of $v_i$. There should be some easy way to get an orthonormal basis from that, but I am not quite seeing it.  
> **username_1**: I think Schonhage's paper "Fast Schmidt orthogonalization and unitary transformations of large matrices" from 1973 answers your question. But I can't find it.  

---

## 0 answers

