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?

Thanks in advance!

best,

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

7 Replies
596 Views

Similar Articles

[PageSpeed] 4

"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?
> 
> Thanks in advance!
> 
> 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?
> > 
> > Thanks in advance!
> > 
> > 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
Reply: