Got Questions? Get Answers.
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:
Speed of matrix norm calculations

Subject: Speed of matrix norm calculations

From: Matt J

Date: 11 Jun, 2013 23:01:10

Message: 1 of 4

Below, I've tested matrix norm calculations via norm(A,p) with p=1,2,inf against more conventional implementations. Except for the p=1 norm, the NORM command seriously lagged behind the alternative in speed performance. Why is this, and shouldn't the implementation of NORM be changed to get the better performance?

A=rand(2000);
%%p=1
tic;
n1=max(sum(abs(A),1));
toc;
tic;
n2=norm(A,1);
toc;
Elapsed time is 0.011953 seconds.

Elapsed time is 0.003040 seconds.

%%p=2
tic;
n1=sqrt( max( eig(A.'*A) ) );
toc;
tic;
n2=norm(A);
toc;
Elapsed time is 1.219832 seconds.

Elapsed time is 3.126588 seconds.

%%p=inf,
tic;
n1=max(sum(abs(A),2));
toc;
tic;
n2=norm(A,inf);
toc;
Elapsed time is 0.016016 seconds.

Elapsed time is 0.038478 seconds.

I think I might understand why the p=2 case is so slow. NORM is using svd(), which is slower than eig, but possibly more stable numerically. However, I cannot understand why it is so much faster than the direct implementation for p=1 and so much slower for p=inf.

Subject: Speed of matrix norm calculations

From: Josh Meyer

Date: 12 Jun, 2013 13:23:41

Message: 2 of 4

Some of this may just be your computer. For example, for p = inf,
norm(A,inf) was 3x faster for me:

tic;
n1=max(sum(abs(A),2));
toc;
tic;
n2=norm(A,inf);
toc;
Elapsed time is 0.027940 seconds.
Elapsed time is 0.009856 seconds.

You're right about norm slowing down from using SVD. Sometimes you can avoid
that by using norm(A,'fro'), which doesn't use SVD (but also calculates a
slightly different quantity):

>> tic; norm(A); toc
Elapsed time is 3.369329 seconds.
>> tic; norm(A,'fro'); toc
Elapsed time is 0.044764 seconds.

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message
news:kp8a7m$ov1$1@newscl01ah.mathworks.com...
> Below, I've tested matrix norm calculations via norm(A,p) with p=1,2,inf
> against more conventional implementations. Except for the p=1 norm, the
> NORM command seriously lagged behind the alternative in speed performance.
> Why is this, and shouldn't the implementation of NORM be changed to get
> the better performance?
>
> A=rand(2000);
> %%p=1
> tic;
> n1=max(sum(abs(A),1));
> toc;
> tic;
> n2=norm(A,1);
> toc;
> Elapsed time is 0.011953 seconds.
>
> Elapsed time is 0.003040 seconds.
>
> %%p=2
> tic;
> n1=sqrt( max( eig(A.'*A) ) );
> toc;
> tic;
> n2=norm(A);
> toc;
> Elapsed time is 1.219832 seconds.
>
> Elapsed time is 3.126588 seconds.
>
> %%p=inf,
> tic;
> n1=max(sum(abs(A),2));
> toc;
> tic;
> n2=norm(A,inf);
> toc;
> Elapsed time is 0.016016 seconds.
>
> Elapsed time is 0.038478 seconds.
>
> I think I might understand why the p=2 case is so slow. NORM is using
> svd(), which is slower than eig, but possibly more stable numerically.
> However, I cannot understand why it is so much faster than the direct
> implementation for p=1 and so much slower for p=inf.

Subject: Speed of matrix norm calculations

From: Matt J

Date: 12 Jun, 2013 14:35:07

Message: 3 of 4

"Josh Meyer" <jmeyer@mathworks.com> wrote in message <kp9sp0$67t$1@newscl01ah.mathworks.com>...
> Some of this may just be your computer. For example, for p = inf,
> norm(A,inf) was 3x faster for me:
==========

I've tried it on 2 different machines, including a pretty powerful dual hexacore desktop, with the same results. Maybe it's version dependent? I'm testing with R2012a and b. Weird...

> You're right about norm slowing down from using SVD. Sometimes you can avoid
> that by using norm(A,'fro'), which doesn't use SVD (but also calculates a
> slightly different quantity):


The Frobenius norm is a pretty different quantity, Josh. I can't imagine when one would interchange one for the other. Incidentally, though, I'm also seeing inferior speed from norm(A,'fro') as compared to a more direct calculation,

tic;
n1=sqrt(sum(A(:).^2));
toc;

tic;
n2=norm(A,'fro');
toc;

Elapsed time is 0.013752 seconds.
Elapsed time is 0.027645 seconds.

Subject: Speed of matrix norm calculations

From: Josh Meyer

Date: 12 Jun, 2013 19:38:36

Message: 4 of 4

>> The Frobenius norm is a pretty different quantity, Josh. I can't imagine
>> when one would interchange one for the other.

Well, yes, but if A is a vector or rank deficient matrix with only 1
singular value then they are the same (I realize thats rare in practice). In
general the Frobenius norm is then an upper bound for the 2-norm, which is
non-trivial.

>>Incidentally, though, I'm also seeing inferior speed from norm(A,'fro') as
>>compared to a more direct calculation

As far as I can tell, the timing behavior you're observing is something that
will be addressed in a future release.
 

Tags for this Thread

No tags are associated with 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