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

Subject: Re: [ublas] Question/request for matrix powers and other stuff
From: Karl Meerbergen (Karl.Meerbergen_at_[hidden])
Date: 2008-10-22 04:13:49

Hi,

I am sorry to correct you guys, but A = X^T J X is not a Jordan
decomposition. It should be
A = X J X^-1. Note that X is in general not a unitary matrix.

What you need to do to do things in a stable way is to use the Schur
decomposition A = X^T S X where S is upper triangular and X unitary (use
lapack's gees). There is a blas routine for multiplying a matrix with a
triangular matrix.

However, I think, the easiest is to compute the power using some clever
algorithm that does the job in log n matrix matrix multiplies.

Best regards,

Karl

Jens Seidel wrote:
> 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
> _______________________________________________
> ublas mailing list
> ublas_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/ublas
>