Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm writing an eigensolver and I'm trying to generate a guess for the next iteration in the solve that is orthogonal to to all known eigenvectors calculated thus far. This means that if I have only one eigenvector, that is say 2 million entries long, I need to generate a vector orthogonal to it. I don't think Gram Schmidt works here because I don't have a set of vectors to orthogonalize. What I have is a single vector, in the first eigensolve, and I need to generate another that is orthogonal.

So, in summary: given one vector, create from nothing another vector which is orthogonal to it. The method must support N-Dimensional vectors (where N could be millions).

I should add that writing a generalized cross product algorithm is not appealing. I'd prefer another way.

share|improve this question
2  
Are there any other constraints? Otherwise, let $a$ be the given vector. If $a_1=0$, then $(1,0,0,\dots)$ works; if $a_2=0$, then $(0,1,0,0,\dots)$ works; otherwise, $(a_2,-a_1,0,0,\dots)$ works. –  Klaus Draeger Feb 6 '12 at 17:21
    
Guess (perhaps by coin flipping) the first say 7/8 of the coordinates, and then use guessing or algebra to determine the rest. This method will rarely fail, and usually because some small set of coordinates are supposed to be zero instead of nonzero. Gerhard "Ask Me About System Design" Paseman, 2012.02.06 –  Gerhard Paseman Feb 6 '12 at 17:21
    
Very useful comments, thank you. –  wavepacket Feb 6 '12 at 17:41

2 Answers 2

up vote 1 down vote accepted

Suppose the vector is $(x_1,x_2,\dots)$. The following algorithm should work:

  1. If $x_1=0$ then take $(1,0,0,\dots)$.

  2. If $x_1$ is non-zero and $x_2=0$ then take $(0,1,0,0,\dots)$.

  3. If $x_1$ and $x_2$ are non-zero then take $(-x_2,x_1,0,0,\dots)$

share|improve this answer
    
This seems to be a popular answer. I'll give it a shot, thanks. –  wavepacket Feb 6 '12 at 17:41
    
Just for the record - 2 and 3 are in fact applications of the same rule :-) –  Vladimir Dotsenko Feb 6 '12 at 18:56

Actually you might use Gram Schmidt here.

Given a set of ortogonal vectors $x_1,x_2,\ldots,x_k$ you can use Gram-Shmidt algorithm for set of vectors $\{x_1,x_2,...,x_k,e_i}$ adding basis vector to system of ortogonalysed vectors (note that you need use Gram Schmidt procedure only to find last vector since first k vectors are already orthogonal). Then (since vectors $e_1,e_2,\ldots,e_{k+1}$ are linearly independent) for some i between 1 and k+1 Gram Schmidt will give you non-zero vector which is ortogonal to given vectors $x_1,x_2,\ldots,x_k$

So to find a guess you simply need to use Gram Schmidt procedure several times (no more than k+1 for the first guess and no more then two times for next guesses).

To simplify this procedure you can do this only with first $k+1$ coordinates of vectors, so you will find a vector of form $(y_1,y_2,\ldots,y_{k+1},0,0,\ldots)$. Answers of Kapil and Klaus are actually equivalent to using this route.

share|improve this answer
    
Or just choose the next vector randomly. In particular, what's wrong with doing Gram-Schmidt to a set of randomly generated vectors? –  Deane Yang Feb 6 '12 at 20:10
    
nothing wrong I guess, don't know if probabilistys algorithm qualifies as an answer to op, so I chose deterministic one. –  Ostap Chervak Feb 7 '12 at 20:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.