joelib-devel

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

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

Hi Oleg,

please give links and references to literature and any further ideas and 
implemtations ... not that this means i will implement all those things 
... but lets discuss them.

As far as i know there is a faster approach using eigenvalues, but i 
have read it is not as general for all kind of weighted adjacency 
matrices, so do you know if this is correct?

Kind regards, Joerg

> "The characteristic polynomial is calculated by using the Le
> Verrier-Faddeev-Frame method, which uses a framework of recursive matrix
> operations." -- this is prety computationaly demanding method I sugest using
> optimizied eigen values calculation algorithm (BLAS for symetric matrices)
> and with the resulting eigenvalues one can easy calculate coeficients of the
> characteristic polynomial.
> 
> Oleg Ursu,
> 
> 
>  
> 
> -----Original Message-----
> From: qsa...@li...
> [mailto:qsa...@li...] On Behalf Of
> qsa...@li...
> Sent: Monday, February 07, 2005 6:27 AM
> To: qsa...@li...
> Subject: Qsar-devel digest, Vol 1 #102 - 1 msg
> 
> Send Qsar-devel mailing list submissions to
> 	qsa...@li...
> 
> To subscribe or unsubscribe via the World Wide Web, visit
> 	https://lists.sourceforge.net/lists/listinfo/qsar-devel
> or, via email, send a message with subject or body 'help' to
> 	qsa...@li...
> 
> You can reach the person managing the list at
> 	qsa...@li...
> 
> When replying, please edit your Subject line so it is more specific than
> "Re: Contents of Qsar-devel digest..."
> 
> 
> Today's Topics:
> 
>    1. New JOELib2 release: bug fix + characteristic polynomials (Joerg
> Wegner)
> 
> --__--__--
> 
> Message: 1
> Date: Sun, 6 Feb 2005 15:48:45 +0100 (MET)
> From: Joerg Wegner <we...@in...>
> To: flo...@st...,
> 	fro...@in...,
> 	joelib <joe...@li...>,
> 	joe...@li..., qsa...@li...
> Cc: chr...@un...
> Subject: [QSAR-devel] New JOELib2 release: bug fix + characteristic
> polynomials
> 
> Hi all,
> 
> minor bug fix release (atom label caching indexing for last atom in a
> molecule, for some properties only) and minor feature enhancement
> (characteristic polynomial).
> 
> After looking for a reasonable interpretation for eigenvalues of the
> adjaceny matrix i have found the analogy to the hueckel matrix.This is
> fantastic, but not really general for all weighted adjaceny matrices, with
> user defined atom and bond labels.
> 
> Nontheless there exists still a much better analytical interpretation of the
> (weighted) adjaceny matrix (with atom and bond labels) which is called the
> characteristic polynomial.
> If the polynomials (their coefficients) of two graphs are identical then
> those graphs are isospectral (spectral theory of graphs).
> 
> Using the Heilbronner theorem, we can check and interpret substructural
> fragments, at least on a linear fragment level.
> 
> Heilbronner theorem:
> P(G)=P(G-eij)-P(G-vi-vj)-2*sum(P(G-Z))
> 
> P(G) is the characteristic polynomial in its general form any edge eij
> G-eij: Graph without this edge
> G-vi-vj: Graph without edge atoms
> sum(P(G-Z)): Sum over ALL rings Z, which contains eij. Please note that this
> means really all rings and not only the SSSR ring set, so this is quite
> nice, but hard to be calculated.
> 
> The characteristic polynomial is calculated by using the Le
> Verrier-Faddeev-Frame method, which uses a framework of recursive matrix
> operations.
> 
> Kind regards, Joerg Kurt Wegner
> 
> 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)                         
> 
> 
> 
> 
> 
> --__--__--
> 
> _______________________________________________
> Qsar-devel mailing list
> Qsa...@li...
> https://lists.sourceforge.net/lists/listinfo/qsar-devel
> 
> 
> End of Qsar-devel Digest
> 
> 
> 
> -------------------------------------------------------
> This SF.Net email is sponsored by: IntelliVIEW -- Interactive Reporting
> Tool for open source databases. Create drag-&-drop reports. Save time
> by over 75%! Publish reports on the web. Export to DOC, XLS, RTF, etc.
> Download a FREE copy at http://www.intelliview.com/go/osdn_nl
> _______________________________________________
> Qsar-devel mailing list
> Qsa...@li...
> https://lists.sourceforge.net/lists/listinfo/qsar-devel
> 


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

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