[Joelib-devel] Re: [QSAR-devel] RE: Qsar-devel digest, Vol 1 #102 - 1 msg

[Joerg K. W. <we...@in...>]

Hi Oleg,

thanks a lot for the details (Matlab is magic and has such a nice Java 
connection) and Trinajstic says:

LeVerrier-Faddev-Frame Modification:
The adjacency matrix is first diagonalized (e.g. Householder-QL 
algorithm \cite[(chapter 5, ref. 81)]{tri92}) and then the recursive 
approach of LeVerrier-Faddev-Frame is applied. However, Balasubramanian 
\cite[(chapter 5, ref. 149)]{tri92} has shown that the 
LeVerrier-Fasseev-Frame method is more universal than this modification 
in its applicability to direct graphs, signed graphs, and complex graphs.

@BOOK{tri92,
   title = {{C}hemical {G}raph {T}heory},
   publisher = {CRC Press, Florida, U.S.A.},
   year = {1992},
   author = {N. Trinajsti\'{c}},
   isbn = {0--8493--4256--2},
   owner = {wegnerj},
}

Kind regards, Joerg


> Hi,
> 
> The problem of finding coeficients of the characteristic polynomial can be
> divided in two parts:
> 
> 1. calculation of eigen values - for symetric matrices one can use QR
> decomposition or other methods available which are very efficient (see
> Numerical Recipes in C by Saul A. Teukolsky, William T. (Unk) Vetterling,
> William H. Press). All these routines are implemented in BLAS (Fortran) or
> LINPACK (C) see www.netlib.org (searching on sourceforge.net could give you
> implementaions of QR in other programing languages including JAVA)
> The adjacency matrices weighted or not are symmetric so the method described
> above holds for any type of them.
> 
> 2. calculation of the coefficients of characteristic polynomial from eigen
> values. The elegant solutions is given in MATLAB the derivation of the
> coefficients from the eigen values. Below is given a fragment from MATLAB's
> help which ilustrates this:
> 
> The algorithms employed for poly and roots illustrate an interesting aspect
> of the modern approach to eigenvalue computation. poly(A) generates the
> characteristic polynomial of A, and roots(poly(A)) finds the roots of that
> polynomial, which are the eigenvalues of A. But both poly and roots use eig,
> which is based on similarity transformations. The classical approach, which
> characterizes eigenvalues as roots of the characteristic polynomial, is
> actually reversed. If A is an n-by-n matrix, poly(A) produces the
> coefficients c(1) through c(n+1), with c(1) = 1, in
> 
> The algorithm is
> z = eig(A);
> c = zeros(n+1,1); c(1) = 1;
> for j = 1:n
>     c(2:j+1) = c(2:j+1)-z(j)*c(1:j);
> end
> 
> This recursion is easily derived by expanding the product.
> 
> It is possible to prove that poly(A) produces the coefficients in the
> characteristic polynomial of a matrix within roundoff error of A. This is
> true even if the eigenvalues of A are badly conditioned. The traditional
> algorithms for obtaining the characteristic polynomial, which do not use the
> eigenvalues, do not have such satisfactory numerical properties.
> 
> Hope this helps, if you have any further questions about this problem I will
> be glad to assist you.
> 
> Oleg Ursu

-- 
Dipl. Chem. Joerg K. Wegner
Center of Bioinformatics Tuebingen (ZBIT)
Department of Computer Architecture
Univ. Tuebingen, Sand 1, D-72076 Tuebingen, Germany
Phone: (+49/0) 7071 29 78970
Fax: (+49/0) 7071 29 5091
E-Mail: mailto:we...@in...
WWW:    http://www-ra.informatik.uni-tuebingen.de
--
Never mistake motion for action.
                                     (E. Hemingway)

Never mistake action for meaningful action.
                                (Hugo Kubinyi,2004)