- ...matlab,
- MATLAB is a registered trademark of
The MathWorks, Inc.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
Software)
- http://gams.nist.gov,
developed by NIST (National Institute of Standards and
Technology).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
NETLIB.
- http://www.netlib.org
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... constant.
- The word pencil
arises historically, because the set of all matrices
of the form for constant , constant , and varying
forms a ``line'' of matrices in matrix space, and this resembles
a ``pencil'' or beam of light.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... form,
- It is usually called
staircase form in the literature, but we find Jordan-Schur more
appropriate.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... random,''
- For example, choose each
entry independently and randomly from
or any other open interval of real numbers.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
- In the case of Hermitian eigenproblems, we mentioned the ability to
count the number of eigenvalues in an interval
.
This can sometimes be done for sparse Hermitian matrices much more
cheaply than computing the eigenvalues in
.
Although such counting algorithms exist for the
NHEP [32],
their costs are similar to transformation methods that
actually compute the eigenvalues, so we do not pursue them.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ....
- For example, is identically zero for
the 1-by-1 pencil
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... form,
- It is usually called
staircase form in the literature, but we find Weierstrass-Schur more
appropriate.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ....
- To see this in the generic case when all the eigenvalues are distinct,
multiply
by and
by to get
.
implies that
must be diagonal,
whence
is also diagonal.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... random,''
- For example,
choose each entry independently and randomly from or any other
open interval of real numbers.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
eigenvector.
- These blocks look like
, where
is a Jordan block with 0 eigenvalue.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... users.
-
In the case of GHEPs, we mentioned
the ability to
count the number of eigenvalues in an interval
.
This can sometimes be done for sparse Hermitian pencils much more
cheaply than computing the eigenvalues in
.
Although such counting algorithms exist for the regular
GNHEP [32],
their costs are similar to transformation methods that
actually compute the eigenvalues, so we do not pursue them.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... out.
- Note that ``direct'' methods must still iterate, since
finding eigenvalues is mathematically equivalent to finding zeros of
polynomials, for which no noniterative methods can exist. We
can call a method direct if experience shows that it (nearly) never fails
to converge in a fixed number of iterations.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
MATLAB.
- It has been announced that an LAPACK-based
numerics library will be part of the next major release of MATLAB;
see The Newsletter for MATLAB, Simulink and Toolbox Users, Winter 2000,
available at
http://www.mathworks.com/company/newsletter/clevescorner/winter2000.cleve.shtml
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...eig.
-
MATLAB checks to see whether the argument of eig is symmetric or
not and uses the symmetric QR algorithm when appropriate.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ....
- There is now a much better algorithm for constructing and applying
these transformations; see D. Sorensen, Deflation for Implicitly Restarted
Arnoldi Methods, CAAM Technical Report, TR 98-12, Rice University,
1998 (revised August 2000).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... matrix
- Deflation with approximate
eigenvectors may introduce an error of order on the
eigenvalues, provided that the computed eigenvalues are well separated
from the remaining ones [353, Section 5.1].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
- When is ill-conditioned, incorporating pivoting into the Cholesky
decomposition can improve the numerical stability of the process [472].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... large.
- Exactly how large is too large is an ambiguous
notion and
should generally be dealt with on a case-by-case basis.
Usually one may regard any number over 1000 as too large
for condition numbers.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...kapj82,sun98,hihi98.
- Kahan, Parlett, and
Jiang [256, Theorem 1]
gave only optimal norms for
.
Take and
to see that
has the same 2-norm and Frobenius norm as .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
MATLAB.
- It has been announced that an LAPACK-based
numerics library will be part of the next major release of MATLAB;
see The Newsletter for MATLAB, Simulink and Toolbox Users, Winter 2000,
available at
http://www.mathworks.com/company/newsletter/clevescorner/winter2000.cleve.shtml
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... called.
- This
code makes very mild assumptions about floating point
arithmetic. It will work on machines with a guard digit in
add/subtract or on those binary machines without guard digits
which subtract like the Cray X-MP, Cray Y-MP, Cray C-90, or Cray-2.
It could conceivably fail on hexadecimal or decimal machines
without guard digits, but we know of none.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... method
- Note that
a direct method must still
iterate, since finding eigenvalues is mathematically equivalent to
finding zeros of polynomials, for which no noniterative methods can exist.
We call a method direct if experience shows that it (nearly) never fails
to converge in a fixed number of iterations.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
MATLAB.
- It has been announced that an LAPACK-based
numerics library will be part of the next major relase of MATLAB;
see The Newsletter for MATLAB, Simulink and Toolbox Users, Winter ,
available at
http://www.mathworks.com/company/newsletter/clevescorner/winter2000.cleve.shtml
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ....
- There is now a much better algorithm for constructing and applying
these transformations; see D. Sorensen, Deflation for Implictly Restarted
Arnoldi Methods, CAAM Technical Report, TR 98-12, Rice University,
1998 (revised August 2000).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...lanc50.
- Historical note: It appears that Lanczos
did not know Krylov's work.
Ostrowski informed Lanczos about the early parallel work of Krylov.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
- A version of the algorithm that enhances numerical stability at the cost
of some extra inner products is described in R. W. Freund, Using Krylov
subspace methods with inexact deflation for reduced-order model.
Bell Labs Numerical Analysis Manuscript, August 2000.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...
MATLAB.
- It has been announced that an LAPACK-based
numerics library will be part of the next major release of MATLAB;
see The Newsletter for MATLAB, Simulink and Toolbox Users, Winter
available at
http://www.mathworks.com/company/newsletter/clevescorner/winter2000.cleve.shtml
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... product.
- The
inner product between two vectors and is defined
as
. If is symmetric and indefinite, then
is a pseudo-inner product. It violates the condition
for all in the definition of a
standard inner product.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... problem:
- The term ``linear'' is in
quotation marks because appears in the eigenvectors as well.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...equivalent
-
Two matrix polynomials and
of size are called equivalent if
for some
matrix polynomials and
with constant nonzero determinants (unimodular).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... generalization,
- See the book's homepage, ETHOME,
for access to the software described in this section.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... vectors,
- Over complex numbers, we always
take the real part of .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.