.. _EigSolution:

The Solution to the Eigenvalue Problem
======================================

We will focus on two orthogonal iterative algorithms that are fairly
simple, yet quickly find accurate eigenvalues. John Francis, introduced
in :ref:`EigHistory`, developed these algorithms. The second
algorithm, called the *Francis algorithm*, establishes the foundation
for eigensystem solutions in modern software such as MATLAB. The ``eig``
function in MATLAB uses the *QZ algorithm* for dense matrices. QZ finds
the generalized eigendecomposition, which is the factorization
:math:`\mathbf{A\,X} = \mathbf{B\,X\,\Lambda}`. If matrix :math:`\bf{B}`
is an identity matrix, then we have the more common eigenvalue problem.
Indeed, the QZ algorithm is an extension of the Francis algorithm.
Although not as closely related, the Krylov algorithm used with sparse
matrices, [1]_ is also derived from the Francis
algorithm [WATKINS11]_.

Before describing Francis's two algorithms, we will discuss the similarity
requirement for diagonalization algorithms and introduce two foundational
algorithms to eigendecomposition---the Hessenberg and Schur decompositions.

.. index:: generalized eigendecomposition
.. index:: QZ algorithm

.. rubric:: Footnote

.. [1]
   Problems related to artificial intelligence and machine learning make
   use of sparse matrices, which are huge matrices dominated by zeros.

**Contents**

.. toctree::
   :maxdepth: 2

   similar
   strategy
   hess
   Schur
   Symmetric
   QReig
   SchurFrancis
   converge
   eigenvect