Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #60801

Re: fast matrix determinant

Show all headers | View raw

On 14.06.2017 18:05, hum9 wrote:
> On 12.06.2017 17:14, krishna.myneni@ccreweb.org wrote:
>> Hi Marcel,
>>
>> I need a fast determinant to write some pedagogical code
>> for illustrating a molecular physics calculation. It is
>> to be used for solving the eigenvalue problem,
>>
>>      D( H - lambda×S ) = 0
>>
>> where H and S are N×N matrices, and lambda(s) are the
>> eigenvalue(s) to be found. D() is, of course, the
>> determinant operator. This form of the eigenvalue
>> problem is typical in molecular physics calculations,
>> when the basis set of eigenfunctions are non-orthogonal.
>>
>> The matrix S, consists of the inner products, of the N
>> eigenfunctions, and it would simply be the identity
>> matrix if the N eigenfunctions were orthonormal.
>> Typically, the hard part in setting up the problem is
>> evaluating the elements of H and S, each of the elements
>> requiring the evaluation of a multi-dimensional integral.
>> Nevertheless, when N becomes large, efficient evaluation
>> of the determinants is needed, particularly in searching
>> for the eigenvalues.
>>
>> A simple way of solving the equation, once the matrix
>> elements of H and S have been computed in the basis set,
>> is to simply use the determinant equation within a root
>> finder, to search for the values of lambda which satisfy
>> the equation. This is conceptually simple and straight-
>> forward to implement, but it's probably not the most
>> computationally efficient method -- there are probably
>> much better techniques available in a linear algebra
>> library. But, for pedagogical use, it's nice. Typically,
>> we are interested in only the lowest eigenvalue.
>>
>> Krishna
>>
> 
> Recently, after your post, I have found something that
> could be useful:
> 
> 
> A symbol between '[' ']' represents a matrix,
> between '{' '}' represents vector,
> ^T   means transpose
> ^-1  means inverse of matrix.
> 
> Theorem (proposition):
> 
> Be a real symmetric matrix [A] NxN  with N distinct nonzero eigenvalues
> and [C] its transformation matrix into orthonormal basis of [A]
> eigenvectors.
> 
> Then, for very small perturbation [dA] (Norm([dA] << Norm([A]))
> will result delta eigenvalues dL, for every index k, 1 <= k <= N
> 
> dLk = Bkk  ,where [B] = [C]^T * [dA] * [C]
> 
> 
> 
> <Proof/
> 
> [A] is a symmetric matrix NxN, with N distinct eigenvalues.
> That means:
> 
>       1) eigenvectors {x}i, 1 <= i <= N are linear independents
> 
>       2) for every i j,   1 <= i != j <=N,   {x}i^T * {x}j = 0.
> 
> ---
> 3)   [A]*{x}=L*(x).
> 
> For a very small perturbation [dA] will follows:
> 
> [A + dA] * {x + dx} = (L + dl) * {x + dx} <=>
> 
> [A]*{x} + [A]*{dx} + [dA]*{x} + [dA]*{dx}
>      =
> L*{x} + L*{dx} + dL*{x} + dL*{dx}
> 
> using 3)   =>
> 
> [A]*{dx} + [dA]*{x} + [dA]*{dx}
>       =
> L*{dx} + dL*{x} + dL*{dx}
> 
> For Norm([dA]) << Norm([A]) , second order terms are negligible, so
> 
> [A]*{dx} + [dA]*{x} = L*{dx} + dL*{x} <=>
> 
> ([A] - L*[I])*{dx} = ([I]*dL - [dA])*{x} <=>
> 
> For every 1 <= k <= N:
> 
> 4)   ([A] -Lk*[I]) * {dx}k = ([I]*dLk - [dA]) * {x}k
> 
> Using 1), vector {dx}k can be expressed in terms of eigenvectors {x}i, so
> 
> {dx}k  =  SUM(Fik * {x}i) =>
> 
> ([A] - Lk*[I]) * {dx}k = ([A] - Lk*[I]) * SUM(Fik * {x}i)
>       =
> SUM(Fik * ([A] - Lk*[I])*{x}i ) =
> SUM(Fik * ([A]*{x}i - Lk*[I]*{x}i) ) =
> SUM(Fik * (Li*{x}i  - Lk*{x}i) ) =
> SUM(Fik * (Li - Lk)*{x}i )
> 
> So 4)   becomes
> 
> SUM(Fik * (Li - Lk)*{x}i ) = ([I]*dLk - [dA]) * {x}k
> 
> multiplying at left side of equality with Transpose of {x}k results
> 
> {x}k^T * SUM(Fik * (Li - Lk)*{x}i  = {x}k^T * ([I]*dLk - [dA]) * {x}k   <=>
> 
> SUM(Fik * (Li -Lk) * {x}k^T * {x}i = {x}k^T * ([I]*dLk - [dA]) * {x}k
> 
>  From 2) results that for i != k  {x}k^T * {x}i = 0,
> also for i=k,  Li - Lk = 0, so left side of equality becames 0:
> 
> 0 = {x}k^T * ([I]*dLk - [dA]) * {x}k
> 
> if we note unity eigenvector {v}k = {x}k/Norm({x}k):
> 
> 0 = {v}k^T *  ([I]*dLk - [dA]) * {v}k
> 
> 
> Transforming bilinear form into orthonormal basis of eigenvectors,
> equality becames:
> 
> 5)   0 = {e}k^T * ([C]^T * ([I]*dLk - [dA]) * [C]) * {e}k
> 
>     ,with {e}k versor of orthonormal eigenvalues basis.
> 
> Let's note:
> 
> [D] = [C]^T * ([I]*dLk - [dA]) * [C]  <=>
> 
> [D] = [C]^T*[I]*[C] * dLk  -  [C]^T*[dA]*[C]  <=>
> 
> [D] = [I]*dLk - [C]^T*[dA]*[C]
> 
> 
> Let's note  [B] = [C]^T*[dA]*[C]  ,so
> 
> 
> [D] = [I]*dLk - [B]  ,so 5)   becames:
> 
> 
> 0 = {e}k^T * ([I]*dLk - [B]) * {e}k  <=>
> 
> 0 = {e}k^T * [I] * {e}k * dLk  -  {e}k^T * [B] * {e}k  <=>
> 
> 0= dLk - Bkk <=>
> 
> *************
> * dLk = Bkk *
> *************
> /Proof>
> 
> Quickly  tested for matrix
> 
> 0 1
> 1 0
> 
> with small perturbation [dA]
> 
> a11 a12
> a21 a22
> 
> ,aij << 1
> 
> and it holds :)
> 
> 
> Have a nice day,
> hum9


It was demonstrated that left side of equality 4) is zero:
	([A] -Lk*[I]) * {dx}k = 0
That means delta-eigenvector is also an eigenvector of [A]!

That means for an eigenvalue Lk of [A], perturbed eigenvector
{x+dx}k is collinear with unperturbed eigenvector of {x}k.

So theorem can be reformulated:

<Theorem>
If real NxN matrix [A] has N orthonormal eigenvectors,
with matrix [C] of orthonormal eigenvectors as columns.

In the case of small perturbation of [A], for every
unperturbed eigenvector {x} corresponds an perturbed
eigenvector {x+dx} collinear with {x}.

Changing basis by [C] to a small perturbed version of [A]
will result an slight perturbed diagonal matrix with small
perturbed eigenvalues on its diagonal.
</Theorem>

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-10 10:29 -0700
  Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-12 05:41 -0700
    Re: fast matrix determinant mhx@iae.nl - 2017-06-12 06:03 -0700
      Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-12 07:14 -0700
        Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-12 07:28 -0700
        Re: fast matrix determinant mhx@iae.nl - 2017-06-12 11:21 -0700
          Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-12 16:39 -0700
        Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-14 18:05 +0300
          Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-14 11:05 -0700
            Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-14 21:37 +0300
          Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-15 09:59 +0300
            Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-15 03:30 -0700
              Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-15 17:57 +0300
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-15 19:06 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 10:21 +0300
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 03:38 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 15:58 +0300
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 06:04 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 16:19 +0300
                Re: fast matrix determinant mhx@iae.nl - 2017-06-16 03:58 -0700
                Re: fast matrix determinant albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-06-16 13:39 +0200
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 05:58 -0700
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 05:12 -0700
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 05:40 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 17:50 +0300
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 13:39 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-17 10:01 +0300
                Re: fast matrix determinant mhx@iae.nl - 2017-06-17 01:31 -0700
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-17 15:24 -0700
            Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-15 17:59 +0300
          Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 10:11 +0300
            Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-17 09:20 +0300
      Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-13 16:43 -0700
        Re: fast matrix determinant mhx@iae.nl - 2017-06-13 22:04 -0700
        Re: fast matrix determinant mhx@iae.nl - 2017-06-14 12:23 -0700
          Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-14 18:31 -0700
    Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-15 19:13 -0700

csiph-web