f

#### Fast Matrix*Diagonal*Matrix operation

```Hi there,

I have a code that computes Q'*D(t)*Q many times. Here Q is a fixed mxn matrix with m < n, while the diagonal matrix D depends on the iteration t.

Because I have so many iterations that the operation slows done the entire process.

I am wondering if there is any way to obtain Q'*D(t)*Q as fast as possible. Maybe from the result of Q'*Q or some kind of decomposition of Q'*Q?

best,

Gongguo
```
 0
Gongguo
1/31/2011 10:31:05 PM
comp.soft-sys.matlab 211266 articles. 22 followers. lunamoonmoon (257) is leader.

7 Replies
655 Views

Similar Articles

[PageSpeed] 14

```"Gongguo Tang" wrote in message <ii7d79\$lto\$1@fred.mathworks.com>...
> Hi there,
>
> I have a code that computes Q'*D(t)*Q many times. Here Q is a fixed mxn matrix with m < n, while the diagonal matrix D depends on the iteration t.
>
> Because I have so many iterations that the operation slows done the entire process.
>
> I am wondering if there is any way to obtain Q'*D(t)*Q as fast as possible. Maybe from the result of Q'*Q or some kind of decomposition of Q'*Q?
>
>
> best,
>
> Gongguo

I think it is unlikely that there is a shortcut using Q'*Q or decomposition thereof.  More likely is if you could a snippet of your code, someone could suggest a more efficient approach
```
 0
proecsm
2/1/2011 1:35:04 AM
```On Jan 31, 11:31=A0pm, "Gongguo Tang" <tanggong...@gmail.com> wrote:
> Hi there,
>
> I have a code that computes Q'*D(t)*Q many times. Here Q is a fixed mxn m=
atrix with m < n, while the diagonal matrix D depends on the iteration t.
>
> Because I have so many iterations that the operation slows done the entir=
e process.
>
> I am wondering if there is any way to obtain Q'*D(t)*Q as fast as possibl=
e. Maybe from the result of Q'*Q or some kind of decomposition of Q'*Q?

Sounds like you might want to have a look at
how the Householder transform helps speed up
the computation of eigenvalues of symmetric
matrices.

Check out the appropriate chapters of

Golub & van Loan: "Matrix Computations" (1996)

Rune
```
 0
Rune
2/1/2011 4:39:39 AM
```"Gongguo Tang" wrote in message <ii7d79\$lto\$1@fred.mathworks.com>...

>
> I am wondering if there is any way to obtain Q'*D(t)*Q as fast as possible. Maybe from the result of Q'*Q or some kind of decomposition of Q'*Q?
>

I'm pretty sure the answer is: no, it's not possible.

Bruno
```
 0
Bruno
2/1/2011 7:18:03 AM
```Hi proecsm,

Thanks for your reply. The first two lines below are my codes for computing Q'*D(t)*Q, where D(t) = diag(sig3) and sig3 changes every iteration.  I still need several other lines to implement additional computations.

I would appreciate if anyone could speed up the code.

----------------
Qtmp = bsxfun(@times,Q.',sig3');
H = Qtmp*Q;
p = sqrt(-eta)*sig2./sig1;
H = H - bsxfun(@times,p,p');
H(1:(N+1):end) = diag(H) + sig1 - sig2.^2./sig1;
-------------------------------------

best,

Gongguo
"proecsm" wrote in message <ii7o08\$lf\$1@fred.mathworks.com>...
> "Gongguo Tang" wrote in message <ii7d79\$lto\$1@fred.mathworks.com>...
> > Hi there,
> >
> > I have a code that computes Q'*D(t)*Q many times. Here Q is a fixed mxn matrix with m < n, while the diagonal matrix D depends on the iteration t.
> >
> > Because I have so many iterations that the operation slows done the entire process.
> >
> > I am wondering if there is any way to obtain Q'*D(t)*Q as fast as possible. Maybe from the result of Q'*Q or some kind of decomposition of Q'*Q?
> >
> >
> > best,
> >
> > Gongguo
>
> I think it is unlikely that there is a shortcut using Q'*Q or decomposition thereof.  More likely is if you could a snippet of your code, someone could suggest a more efficient approach
```
 0
Gongguo
2/3/2011 8:57:03 PM
```Hi Bruno,

Could you explain why it is so? Thanks.

best,

Gongguo
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ii8c3b\$a9r\$1@fred.mathworks.com>...
> "Gongguo Tang" wrote in message <ii7d79\$lto\$1@fred.mathworks.com>...
>
> >
> > I am wondering if there is any way to obtain Q'*D(t)*Q as fast as possible. Maybe from the result of Q'*Q or some kind of decomposition of Q'*Q?
> >
>
> I'm pretty sure the answer is: no, it's not possible.
>
> Bruno
```
 0
Gongguo
2/3/2011 8:58:04 PM
```"Gongguo Tang" wrote in message <iif4qv\$a1d\$1@fred.mathworks.com>...
> Hi proecsm,
>
> Thanks for your reply. The first two lines below are my codes for computing Q'*D(t)*Q, where D(t) = diag(sig3) and sig3 changes every iteration.  I still need several other lines to implement additional computations.
>
> I would appreciate if anyone could speed up the code.
>
> ----------------
> Qtmp = bsxfun(@times,Q.',sig3');
> H = Qtmp*Q;
> p = sqrt(-eta)*sig2./sig1;
> H = H - bsxfun(@times,p,p');
> H(1:(N+1):end) = diag(H) + sig1 - sig2.^2./sig1;
> -------------------------------------

I think we have to see more. The real question is, what do you intend to do with H? If all you eventually do with H is multiply it with a vector, then you don't have to compute H at all.
```
 0
Matt
2/3/2011 9:15:20 PM
``` >H = H - bsxfun(@times,p,p');

also, note that if p is a vector, then this is just

H=H-p*p'
```
 0
Matt
2/3/2011 9:16:04 PM