Re: Matrix equation


Jani Huhtanen wrote:
>...
>If this is applied recursively starting from say 1x1
> matrix (scalar) one can get inverse of R with O(k^3) complexity (with
> 2*k^3 + 3*k^2 + k mults), where k is the order (or size of the matrix R).

This is wrong. If I calculated correctly the amount of mults is given by
sum(k^2) from k=2 to K, where K is the final order (size of R). So the
correct amount of multiplications is (k^3)/3 + (k^2)/2 + k/6 - 1.

>
> Isn't this of the same complexity as inversion of symmetric positive
> definite matrix through Cholesky decomp?

According to Golubs and van Loans "Matrix Computations 2nd ed." Cholesky
decomposition is O(n^3) and requires n^3/3 flops. This n^3/3 is an
approximation and it contains also additions.

As a conclusion I think that the performance of the recursive calculation of
the R^-1 is comparable to Chol.decomp. Also if Alan Tan didn't do any
mistakes in his proof, this new (?) algorithm works for all symmetric
matrices (Am I right Alan?).

Now the question is: Is this a _new_ algorithm?
And is there even better ways to accomplish this (ie. finding the mse
associated with each predictor order and finding the R^-1 of the "optimal"
order)?

--
Jani Huhtanen
Tampere University of Technology, Pori
.

Relevant Pages

  • Re: Matrix equation
    ... Alan Tan showed how my equation can be simplified. ... Particularly intresting is the equation for R^-1. ... definite matrix through Cholesky decomp? ... linear predictor for "free" because I can check the minimum error at every ...
    (comp.dsp)
  • Re: Golub-Reinsch SVD algorithm by Harold Norman + soft copy avaliable
    ... The code is actually based on Golub-Reinsch algorithm and it is ... >AUKBC Research centre ... Matrix Computations John Hopkins Press ...
    (sci.math.num-analysis)