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

Groups > comp.lang.forth > #60885

Re: fast matrix determinant

Show all headers | View raw

On 16.06.2017 10:11, hum9 wrote:
> 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

I reviewed proof paper and I found that:
{x}k^T * ([A] -Lk*[I]) * {dx}k = 0
which means that collinearity is not part is false.

> 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.
> 
That part is false.

> So theorem can be reformulated:
> 
> <Theorem>
> If real NxN matrix [A] has N orthonormal eigenvectors,
> with matrix [C] of orthonormal eigenvectors as columns.
>

<False>


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

> 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