Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
cholesky factorization

Subject: cholesky factorization

From: Dimitar Dimitrov

Date: 9 Oct, 2007 09:20:57

Message: 1 of 3

Hello,

I have B = eye(n,n) + A'*A

where, A is an upper triangular matrix.
I want to make a Cholesky factorization of B.
So, one way is to make the product A'*A, then sum with
eye(n,n) and then make chol(B), however if "n" is large,
computing A'*A is time consuming. Is there a way to use the
fact that A'*A is already in a "Cholesky factorized" form?
In other words, can we compute chol(B) without having to
make the actual multiplication A'*A.

Thank you
Dimitar

Subject: cholesky factorization

From: John D'Errico

Date: 9 Oct, 2007 11:45:15

Message: 2 of 3

"Dimitar Dimitrov" <mail_mitko@mathworks.com> wrote in message <fefh5p
$g28$1@fred.mathworks.com>...
> Hello,
>
> I have B = eye(n,n) + A'*A
>
> where, A is an upper triangular matrix.
> I want to make a Cholesky factorization of B.
> So, one way is to make the product A'*A, then sum with
> eye(n,n) and then make chol(B), however if "n" is large,
> computing A'*A is time consuming. Is there a way to use the
> fact that A'*A is already in a "Cholesky factorized" form?
> In other words, can we compute chol(B) without having to
> make the actual multiplication A'*A.

Just thinking here...

If you know that A is upper triangular, then
you also know its QR factorization.

  Q == eye(n,n)
  R == A

Now, you wish to find the Cholesky factor of B,
which is equivalent to computation of the QR
factorization for the matrix

  C = [A;eye(n,n)]

since C'*C == A'*A + eye(n,n)

So it might be more efficient to compute the
factor you need by row updates to the QR.
Look at qrupdate or qrinsert. A nice feature
of this approach is it will be much more
accurate since you need never compute A'*A,
an accuracy destroying computation, besides
the time wasted to build it.

Unfortunately, since you need to make n
rank 1 updates, my guess is that the total
time may be similar in the end, but at least
you should gain in accuracy.

John

Subject: cholesky factorization

From: Dimitar Dimitrov

Date: 9 Oct, 2007 13:01:59

Message: 3 of 3

Hello John,

I checked qrupdate and found that actually there is a
function cholupdate (both can be used).
Thank you for pointing me in the right direction!

Best regards,
Dimitar

"John D'Errico" <woodchips@rochester.rr.com> wrote in
message <fefpkb$3lb$1@fred.mathworks.com>...
> "Dimitar Dimitrov" <mail_mitko@mathworks.com> wrote in
message <fefh5p
> $g28$1@fred.mathworks.com>...
> > Hello,
> >
> > I have B = eye(n,n) + A'*A
> >
> > where, A is an upper triangular matrix.
> > I want to make a Cholesky factorization of B.
> > So, one way is to make the product A'*A, then sum with
> > eye(n,n) and then make chol(B), however if "n" is large,
> > computing A'*A is time consuming. Is there a way to use the
> > fact that A'*A is already in a "Cholesky factorized" form?
> > In other words, can we compute chol(B) without having to
> > make the actual multiplication A'*A.
>
> Just thinking here...
>
> If you know that A is upper triangular, then
> you also know its QR factorization.
>
> Q == eye(n,n)
> R == A
>
> Now, you wish to find the Cholesky factor of B,
> which is equivalent to computation of the QR
> factorization for the matrix
>
> C = [A;eye(n,n)]
>
> since C'*C == A'*A + eye(n,n)
>
> So it might be more efficient to compute the
> factor you need by row updates to the QR.
> Look at qrupdate or qrinsert. A nice feature
> of this approach is it will be much more
> accurate since you need never compute A'*A,
> an accuracy destroying computation, besides
> the time wasted to build it.
>
> Unfortunately, since you need to make n
> rank 1 updates, my guess is that the total
> time may be similar in the end, but at least
> you should gain in accuracy.
>
> John

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us