From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: Eigenvalue Problems
Date: 21 Jun 1999 15:00:47 GMT
Newsgroups: sci.math.num-analysis
Keywords: computational complexity of eigenvalue-related problems

In article <376120A2.ED60A2CD@wisdom.weizmann.ac.il>,
 "Oren E. Livne" <livneo@wisdom.weizmann.ac.il> writes:
|> Dear Sirs,
|> 
|> I'm a Ph.D. student in numerical analysis.
|> Here's my questions:
|> 1. Given an nxn tridiagonal matrix, what is the complexity (operations
|> amount) for calculating
|>     all eigenvalues?
O(n^2), where the constant depends on the required precision .
holds for QR as well for Sturm sequence (the latter in the case of a hermitian 
matrix)
you need O(1) steps for any eigenvalue, 
any step involves O(n) resp O(n-i) operations
for any 
|> 2. What's the amount for all eigenvalues & eigenvectors in this case?
O(n^3). 
 again, the constant depends on the precision required
any step now involves O(n^2) operations due to the application on the 
evolving eigensystem.
|> 3. What is the answer on these questions for band matrices (symmetric,
|> real if you want, or more general, if you can provide an answer for a
|> more general case)? is it O(n), O(n^2), O(n^3)?
symmetric (hermitian) case. p=bandwidth: O(p^2 n^2) and O(p^2 n^3)
for p<< n 
|> 4. Complexity for expanding a general function in the eigensystem, once
                                ^^^^^^ analytic : 
none, since for f(z)=\sum_{k=0}^{\intfy}a_k z^k 
    f(A) = T \sum_{k=0}^{\infty} a_k diag(\lambda_i^k) T^{-1}
|> computed?
|> 
|> Can you please give refenences on the numerical software 
Golub & van Loan: Matrix computations
Trefethen & Bau : Numerical linear algebra
Demmel : applied numerical linear algebra 

all deal with these matters.
hope that helps
peter
==============================================================================

From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: operation count for QR factorization by householder trans.
Date: 4 May 1999 09:41:52 GMT
Newsgroups: sci.math.num-analysis

In article <Pine.GSO.3.96.990503095259.15661A-100000@saga21.Stanford.EDU>,
 "Andrew T. Yang" <blaz@leland.Stanford.EDU> writes:
|> Hi,
|> 
|> 
|> Why is that the operation count for QR factorization of an  m x n matrix
|> by Householder transformation are 
|> 
|>              (n^2)*m  - (1/3)*(n^3)?
for i=1 to n :
   compute length l_i of current remaining column m-i+1 mult, 1 sqrt
   compute normal u_i    no mult's
   compute beta_i = 1/(l_i*(l_i+abs(a(i,i))) 1 mult , 1 div 
   for j=i+1 to n
      compute scalar product of u_i and a(.,j) , length m-i+1 : m-i+1 mult
      multiply by beta_i, getting factor_i                           1 mult
      subtract factor_i*u_i from a(.,j)                         m-i+1 mult
   done
done

sum_{i=1}^n {  m-i+2 +(n-i)*(2*m-2*i+3) } mult + n div 
                                           
sum_{i=1}^n i  = n*(n+1)/2 
sum_{i=1}^n i^2 = (2*n+1)*n*(n+1)/6 
      
result: dominant term as above.
hope this helps
peter