Subject: SUMMARY: lin.alg.?

From: Vitaly Rassolov <[email-masked]>
Date: Thu, 8 Apr 1999 13:41:46 -0500 (CDT)

Yesterday I posted a question about a search for the basis set in the
orthogonal subspace.  Many thanks to everyone who replied.  There were
three groups of responses:

1. Gram-Schmidt type procedure. This usually works, but its
numerical properties are not very good.

2.  Eigenvalue search (through SVD, or otherwise).

3.  The most suitable for me:  Householder QR decomposition with follow-up
recovery of Q.  The routines are available in LAPACK:  DGEQPF followed by
DOPGTR.  This is probably the most efficient and balanced way.

The question and responses follow:

*****************

Does anyone know the efficient algorithm/subroutine for calculating the
basis in the orthogonal subspace?  Or, more precisely:
  Given N M-dimensional vectors, how to find (M-N) M-dimensional
orthonormal vectors, each of them being orthogonal to the each of the N
original vectors.

This seems to be a very universal problem, yet I couldn't find anything in
LAPACK/NETLIB/Numerical Recipies.

Any help will be very much appreciated

_______

Vitaly Rassolov                      [email-masked]
Chemistry Department                 tel. (847) 491-3423
Northwestern University              fax  (847) 491-7713

From: Zdenko Tomasic <[email-masked]>
To: [email-masked]

try QR  decomposition with pivoting
like in LAPACK's dgeqpf
Q is what you are looking for

ZT

From: Vitaly Rassolov <[email-masked]>
To: Zdenko Tomasic <[email-masked]>

Thanks for your reply.  Is this (in your opinion) an efficient enough
method for the problem (after all, I don't need R)?

From: Zdenko Tomasic <[email-masked]>
To: [email-masked]

yes. assuming you are dealing with dense matrices.
R is often not needed, but is inevitable in this decomposition
besides it is only triangular.

ZT

From: Vitaly Rassolov <[email-masked]>
To: Zdenko Tomasic <[email-masked]>

Thanks again!  Allow me to bug you one last time.  Instead of Q, the
LAPACK subroutines return those Householder reflectors, and reconstructing
Q seems to be quite time consuming (M products of M*M matricies).  Do you
know any alternative QR decomposition subroutines that return Q
explicitly, or is there a simpler way to recover Q in LAPACK?

>From [email-masked] Thu Apr  8 12:03 CDT 1999

hoseholder reflectors (H's) are rather special and their application
is very efficient. DOPGTR routine should form Q for you out of H's.

ZT

From: uccatvm <[email-masked]>
To: [email-masked] (Vitaly Rassolov)

Hi Vitaly,

If I understand you correctly, you are looking for an implementation
of Schmidt orthogonalization. You might try a web search for Schmidt or
Gram-Schmidt. It should also be described in any linear algebra text.

Hope this helps,

Tanja
--
  ====================================================================
     Tanja van Mourik
                                      phone
     University College London        work:   +44 (0)171-504-4665
     Christopher Ingold Laboratories  home:   +44 (0)1895-259-312
     20 Gordon Street                 e-mail
     London WC1H 0AJ                  work: [email-masked]
     United Kingdom                   home: [email-masked]
  ====================================================================

From: Jordi Villa <[email-masked]>
To: Vitaly Rassolov <[email-masked]>
Subject: Re: CCL:lin.alg.? (basis set in the orthog. subspace)

Dear Vitaly,

if I am not wrong you are asking for a
Gram-Schmidt ortogonalization procedure.
You can use:

v_i = N_i [1 - SUM_(k=1)^(i-1) (1 - delta_(ik) )
v_k * v_k^T] * v_i^0

where v_i^0 is the old (non-ortogonalized) vector
and v_i is the new (ortogonalized) one.
I hope you understand the equation (it is a little
bit odd in ASCII)

Best regards

--
Jordi Villa i Freixa
Department of Chemistry
University of Southern California
Los Angeles, CA, USA, 90089-1062
Tlf: 1-(213)-740 7671 Fax: 1-(213)-740 2701
[email-masked]      http://www1.imim.es/~jvilla

>From [email-masked] Wed Apr  7 21:39 CDT 1999
To: Vitaly Rassolov <[email-masked]>

Hi

It looks to me as if you're describing the Gram-Schmidt process
for extending an orthogonal basis. (It's covered to some extent
in Numerical Recipes.) There are some numerical instabilities in
the method, and modifications of it exist (see e.g. Golub and
van Loan, Matrix Computations, Johns Hopkins Press, 1989).

Hope this helps.

Rod
---
R. M. Macrae
Muon Science Laboratory
Institute of Physical and Chemical Research (RIKEN)
Wako, Saitama, Japan

From: [email-masked]

Hey Vitaly,

Your problem could in principle be solved by taking M orthogonal test
vectors of

dimension M (for example the unit vectors:)

(1,0,0,0,0,0,....,0)
(0,1,0,0,0,0,....,0)
(0,0,1,0,0,0,....,0)
(0,0,0,1,0,0,....,0)
(0,0,0,0,1,0,....,0)
 .
 .
 .
(0,0,0,0,0,0,....,1)

You take the first of these and orthonormalize it with respect to the N
starting

vectors. This is then a basis vector in the orthogonal space. You then
take the
second of your test vectors and orthonormalize it with respect to your N
starting vectors and the first basis vector in the orthogonal space. Take
the
third test vector and orhthnormalize with respect to the N starting
vectors and
the two basis vectors in the orthogonal space and so on ...

As orthonormalization procedure many alternatives are available, look for
example for Gram-Schmidt orthonormalization.

While you are doing the successive orthonormalizations, you might
encounter the
problem, that your current test vector doesn't span a dimension in the
orthogonal space. This means, if you are using Gram-Schmidt
orthogonalization at

least, that the current test vector is a linear combination of the N
starting
vectors and the already found basis vectors in the orthogonal space. As
you have

M test vectors and only M-N free dimensions, actually this problem will
arise N
times among your M test vectors. This is why you need M test vectors and
not M-N

test vectors, to find the M-N basis vectors in the orthogonal space.

Every time you encounter the above mentioned problem, you just throw the
test
vector away and take the next one, then the problem solves itself.

If your are using real variables, all dimensions are reasonably populated
and
the symmetry is not interfearing, you will normally not have to throw any
test
vectors away during your algorithm, as it will automatically be the last N
of
your test vectors that are linearly dependant, where you have used only
the
first M-N test vectors to find the M-N sought-after basis vectors of the
orthogonal space.

I hope this was of some help. Good look with the work

Thomas

************************
Thomas Bligaard Pedersen
C.N.R.S. UMR7551
Lab. Chimie Quantique
Universit Louis Pasteur
Strasbourg
FRANCE
************************

To: Vitaly Rassolov <[email-masked]>
From: Darko Babic <[email-masked]>
Subject: Re: CCL:lin.alg.? (basis set in the orthog. subspace)

        Hi!

        One thing you could do is to form a matrix from those N given
M-dimensional vectors as the density matrix is formed from the vectors
representing the occupied molecular orbitals, and then to diagonalize
the matrix.  You should get N eigenvalues different from (greater than)
zero and M-N zero eigenvalues.  The eigenvectors corresponding to zero
eigenvalues are those you are looking for.  Each of them will be ortho-
gonal to the first M eigenvectors, but they might be non-orthogonal
between themselves (depends which subroutine you use for the diagonali-
zation).

        In a formal way: let V_i, i=1...N, denote N given eigenvectors
and let [V_i]_j denote the j-th coordinate of the vector [V_i]_j.  Form
the matrix P: [P]_ij = SUM{k=1...N} [V_k]_i * [V_k]_j and diagonalize
it.  The eigenvectors corresponding to non-zero eigenvalues span the
N-dimensional subspace containing the starting N M-dimensional vectors,
and the remaining eigenvectors span the rest of the space.

        I'm sure there must be another way, too.

                        With best wishes,
                                                        Darko Babic
                                                Institute "Rudjer
Boskovic"
                                                HR-10001 Zagreb, P.O.B.
1016
                                                          Croatia

>From [email-masked] Thu Apr  8 10:14 CDT 1999
Subject: Canonical orthogonalization

Hello,

have a look at paper :
X. Assfeld, and J.-L. Rivail, CHem. Phys. Lett. 263 (1996) 100.
you will find what you are looking for.
C.U.

                                      ...Xav

Ast. Pr. Xavier Assfeld             [email-masked]
Laboratoire de Chimie theorique     (T) 33 3 83 91 21 49
Universite Henri Poincare           (F) 33 3 83 91 25 30
F-54506 Nancy BP 239                http://www.lctn.u-nancy.fr

From: Konrad Hinsen <[email-masked]>
To: [email-masked]
CC: [email-masked]

Such a set of vectors can be obtained as a "side effect" of singular
value decomposition (SVD). I use the SVD routines in LAPACK for this
purposes. What you get is

1) A basis for the subspace spanned by the set of input vectors.
2) A basis for the complementary space, which is what you are
   looking for.

--
-------------------------------------------------------------------------------
Konrad Hinsen                            | E-Mail: [email-masked]
Centre de Biophysique Moleculaire (CNRS) | Tel.: +33-2.38.25.55.69
Rue Charles Sadron                       | Fax:  +33-2.38.63.15.17
45071 Orleans Cedex 2                    | Deutsch/Esperanto/English/
France                                   | Nederlands/Francais
-------------------------------------------------------------------------------