Re: [ublas] Question/request for matrix powers and other stuff

Subject: Re: [ublas] Question/request for matrix powers and other stuff
From: Jens Seidel (jensseidel_at_[hidden])
Date: 2008-10-22 04:02:08

On Tue, Oct 21, 2008 at 04:18:52PM -0400, Daryle Walker wrote:
> On Oct 21, 2008, at 3:25 PM, Gunter Winkler wrote:
>
> [SNIP]
>> In general you can use the following procedure:
>>
>> given: square matrix A
>> compute a the jacobi matrix  A = X^T J X

"jacobi" matrix" should be probably replaced by "Jordan". See
e.g. http://en.wikipedia.org/wiki/Jordan_matrix

A Jordan block has the great advantage that it is trivial
to compute powers of it and every square matrix can be transferred
into such a type (by a base transformation). But this is generally
not numerically stable IIRC.

>> compute J^n
>> compute A^n = X^T J^n X
>>
>> The main problem is the first step which requires the solution of a
>> generalized eigenvalue problem ...

> The code I'm adapting sometimes enters a LOT of zero-values in a row.  
> The original author realized that, since inserting a zero can be 
> expressed as a linear transformation, using the matrix form and raising 

Heh?

> it to a power can _save_ time over inserting each zero manually.  (The 
> original author used a bit-packing scheme for the GF(2) matrices 
> involved, which I'll add later.)  The manual method is by definition 
> linear on the number of zeros added.  Using matrices and powers, 
> especially with square-and-multiply, should represent a savings when the 
> length gets long enough.

I don't understand this :-)

Jens