0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – Klaus Draeger
    Commented Feb 6, 2012 at 17:21
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Feb 6, 2012 at 17:21

3 Answers 3

Reset to default
4
$\begingroup$

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)$

Improve this answer
$\endgroup$
2
  • $\begingroup$ This seems to be a popular answer. I'll give it a shot, thanks. $\endgroup$
    – wavepacket
    Commented Feb 6, 2012 at 17:41
  • 5
    $\begingroup$ Just for the record - 2 and 3 are in fact applications of the same rule :-) $\endgroup$
    – Vladimir Dotsenko
    Commented Feb 6, 2012 at 18:56
0
$\begingroup$

Actually you might use Gram Schmidt here.

Given a set of orthogonal vectors $x_1,x_2,\ldots,x_k$ you can use Gram-Shmidt algorithm for set of vectors $\{x_1,x_2,\ldots,x_k,e_i\}$ adding basis vector to system of orthogonalysed 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 orthogonal 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.

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

I think for a 2m dimensional vector ( a,b,c,d.........z) you can say that ( -z, -x,......... a) is orthogonal where half are negative of their original values However for 2m + 1 dimensional vector you can't straightforwardly say the same ( if you want a non zero orthogonal vector ). But since it is a guess you can keep a zero in the middle i think

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .