Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Computation of the matrix exponential
Replies: 6   Last Post: Feb 10, 2013 5:00 AM

 Messages: [ Previous | Next ]
 luca Posts: 11 Registered: 5/19/10
Re: Computation of the matrix exponential
Posted: May 25, 2010 4:49 AM

On 25 Mag, 07:59, Chip Eastham <hardm...@gmail.com> wrote:
> On May 24, 8:37 pm, luca <luca.frammol...@gmail.com> wrote:
>
>
>
>
>

> > Hi,
>
> > i have the following problem: given a 3x3 real matrix, compute exp(A).
>
> > I need a really fast way to do this. I have searched a bit with
> > google, but it seems to me that
> > computing the matrix exponential is not so simple, at least if your
> > matrix does not have a special
> > structure (for example A=diagonal matrix).

>
> > I have found a simple method that use the diagonalization of A. If A
> > has 3 distinct eigenvalues, than compute
> > A=PDP^-1, where P is the matrix of the eigenvectors, D is a diagonal
> > matrix (whose diagonal elements are
> > the eigenvalues of A). Than, exp(A) = P exp(D) P^-1. Since P^-1 is
> > fast enough and exp(D) is simple
> > to compute, this should be a fast method.

>
> > But, the problem is: i am not sure that the matrix A will always have
> > 3 distinct eigenvalues...what happens
> > if this does not happen? Can i use that formula even if 2 (or all
> > three) eigenvalues are equal?

>
> > Are there any other ways to compute exp(A) in a fast way?
>
> > Thank you,
> > Luca

>
> You'll probably find the "updated" discussion of matrix
> exponentiation by Cleve Moler and Charles Van Loan to be
>
> [Nineteen Dubious Ways to Compute the Exponential of a
>   Matrix, Twenty-Five Years Later]http://www.cs.cornell.edu/cv/ResearchPDF/19ways+.pdf
>
> Your statement that you need to compute the matrix
> exponential "really fast" suggests that you intend
> the reason for doing this might lead to a more focused
> evaluation of algorithms.
>
> regards, chip- Nascondi testo citato
>
> - Mostra testo citato -

Hi Chip,

thank you for your replay. Yes, i need to compute the matrix
exponential during an iterative algorithm.

The algorithm is a second-order minimization one.

Suppose that you have a vector x (of size 8 x 1), computed during the
iterations of the algorithm.
When || x || <= eps, with eps a small real number, there is
convergence.

The method is used to find a homography (3x3 matrix). In practice, one
starts with an estimate of the
homography H', compute the vector x (i will not give other details on
this since it would
require too much space), update the homography using H' = H' *
exp(A(x)).

What is A? A is a 3x3 matrix of the form:

A(x) = sum_i=1..8 (x_i*A_i)

where the A_i are 3x3 matrices. They are chosen to be a basis for the
Lie algebra sl(3). sl(3) is the algebra associated to the group SL(3).
The projective transformation H is in SL(3).
The papers says that :"the exponential map is a homeomorphism between
a neighborhood of I in SL(3) and a neighborhood of the null matrix 0
of sl(3)".

The A_i are constant matrices. They have trace null. The matrix A_i
will have:

1] only one non-diagonal element non null (1)
or
2] two diagonal elements non-null (1 and -1)

Since the methods is such that the vector x will tends to have smaller
and smaller components, if we start with a x sufficiently near to the
null vector,
we can use the above parameterization of H.

This is all.
If you are interested i can give you the paper of reference. I am
working in the field of Computer Vision.

Luca

Date Subject Author
5/24/10 luca
5/24/10 Chip Eastham
5/25/10 Chip Eastham
5/25/10 luca
5/25/10 Chip Eastham
5/29/10 robin
2/10/13 Mircea GURBINA