From: hook@nas.nasa.gov (Ed Hook)
Subject: Re: Lanczos Algorithm
Date: 8 Mar 2000 17:37:31 GMT
Newsgroups: sci.math
Summary: [missing]

In article <38C60A82.221EE8D0@ix.urz.uni-heidelberg.de>,
     Asmus Loewenhaupt <aloewen2@ix.urz.uni-heidelberg.de> writes:

|>               Also I have problems proving and understanding this
|> theorem: 
|> Let Km(A,v) be the krylov-subspace Km(A,v)=span{v, A*v, ..., A^m*v},
|> where A is a (n x n)-Matrice over R an v is a vector. Let p(A) be the
|> minimalpolynomial of v in Respect to A, t.m. the normed polynomial so
|> that p(A)*v=0. Let µ be the degree of p. 
|> Then Kµ(A,v) is invariant under A, and for all m >= µ is
|> Km(A,v)=Kµ(A,v).
|> 

  It's clear that Kµ(A,v) is invariant under A if and only if
  A^{µ+1}v belongs to Kµ(A,v). But µ is the degree of p(A), which
  implies that you can use the relation p(A)v = 0 to write
  A^µ v in terms of the vectors A^{µ-1} v, A^{µ-2} v, ... , Av, v,
  And, then, you can write A^{µ+1} v in terms of A^µ v, ... , Av --
  that is, you can show that A^{µ+1}v lies in Kµ(A,v). Hence,
  Kµ(A,v) is invariant under A.

  For the other claim, note that Kµ(A,v) is (obviously) a subspace
  of Km(A,v) if m > µ; you just need to show the _other_ inclusion.
  But the argument above can be repeated to show, by induction, that
  A^m v lies in Kµ(A,v) for every m > µ. Therefore, Km(A,v) is a
  subspace of Kµ(A,v) if m > µ and the claim follows.

-- 
 Ed Hook                              |       Copula eam, se non posit
 MRJ Technology Solutions, Inc.       |         acceptera jocularum.
 NAS, NASA Ames Research Center       | I can barely speak for myself, much 
 Internet: hook@nas.nasa.gov          |         less for my employer
==============================================================================

From: sci.math.num-analysis@elsner.org (Ulrich Elsner)
Subject: Re: Iterative analysis : convergence
Date: 14 Dec 2000 09:59:44 GMT
Newsgroups: sci.math.num-analysis

According to Eric GUERIN  <eguerin@ligim.univ-lyon1.fr>:
> I need to solve large linear systems involving 200x200 matrices. Such a
> large number of equations implies that I can't use a direct method.

A 200x200 matrix will take about 320 Kbytes memory.  On my machine (a
Pentium-III 800) it takes less than 0.1 second to solve such a system
(using Matlab). Unless your resources are really limited, just use a
direct solver, e.g., from LAPACK http://www.cs.colorado.edu/~lapack/. If
performance matters, make sure your code is well tuned, e.g. by using the
ATLAS BLAS routines http://www.netlib.org/atlas/ .

Iterative methods will (in general) only help if your matrices are
sparse. 

> That's why I'm trying to use iterative methods such as Jacobi,
> Gauss-Seidel.  My problem is that the convergence condition is very
> strict : the spectrum radius must be less than 1.
>
>- Is there other methods less strict regarding convergence conditions ?
>- Is there a way to adapt Gauss-Seidel ?

Modern Krylov subspace based methods (cg, qmr, GRRES,...) should be faster
and converge more often. For a first look at these methods, try

@BOOK{templates,
  author = "R. Barrett and M. Berry and T. Chan and J. Demmel and J. Donato
           and J. Dongarra and V. Eijkhout and R. Pozo and C. Romine and H.
           van der Vorst",
  title = "Templates for the solution of linear systems",
  year = 1994,
  publisher = "SIAM"
}

which can be found as a Postscript file at
http://www.netlib.org/templates/templates.ps


Regards,


Ulrich Elsner

--
Ulrich Elsner, Fak. fuer Mathematik, TU Chemnitz, D-09107 Chemnitz, Germany