Message Boards Message Boards

GROUPS:

Find matrix´s diagonal as fast as the Diagonal[]?

Posted 2 years ago
3458 Views
|
4 Replies
|
3 Total Likes
|

Hello community.

I am studying different ways to find the diagonal of a matrix without using the Diagonal command, just for an operations study, of course I can use Diagonal[], but I wonder if there is a way to simulate this command using other commands, just so that I can learn more about the WL language.

For example the matrix “a” (10000 x 10000) defined by:

SeedRandom[1234]
n = 10000;
a = Table[RandomInteger[9, n], n];

To have a basis of comparison for the study, I get the performance of the Diagonal command:

Diagonal[a]; // AbsoluteTiming

i1

Some attempts (all were slower than Diagonal[]):

Map[a[[#, #]] &, Range@n]; // AbsoluteTiming

i2

Table[a[[i, i]], {i, Length@a}]; // AbsoluteTiming

i3

  • Edited1:

I think I've found a better way than the ones I've tried so far:

Extract[Table[{i, i}, {i, Length@a}]][a]; // AbsoluteTiming

i4

But it still takes about more than twice the time of Diagonal[].

What other ways to find the diagonal of a matrix that are faster than these attempts above without using the Diagonal command? I would love to learn other ways, I could only think of those two ways. Could it also be that, even using Part, there is a faster and simpler way that I haven't thought of? Can anyone teach me others ways (even if they are slower than Diagonal[])? I will be very grateful if anyone can help! Thanks.

4 Replies
Posted 2 years ago

I'll leave the extensive testing up to you, as I am currently not able to, but back when Diagonal[] was not yet implemented, one used either Tr[mat, List] or Transpose[mat, {1, 1}] for the purpose of extracting diagonal elements. A reason to use the latter construct even now, if not for speed, is that it is compilable, as opposed to Diagonal[].

POSTED BY: J. M.
Answer

Thank you so much for the reply J.M.

Tr[] and Transpose[] I had not thought of as a means of finding the diagonal ... they are really very simple and easy to to get the diagonal, very good.

Tr[] had the same performance as Map[] at speed:

Tr[a, List]; // AbsoluteTiming

im5

Now Transpose[], in the speed test, was intermediate between Extract[] and Table[], at least in this large matrix:

Transpose[a, {1, 1}]; // AbsoluteTiming

im6

The biggest performance I had in speed was when I replaced the Table[] from within Extract[] with Transpose[] as follows:

Extract[Transpose@ConstantArray[Range@Length@a, 2]][
   a]; // AbsoluteTiming

im8

The result has not yet reached the speed of Diagonal[], it took almost 40-50% more time, but for now it was the best result.

Thanks J.M. for the ideas! And if you or anyone in the community has any other way, please, I'd love to hear from you.

Posted 2 years ago

A thing you might have to account for in your performance checks is that Table[RandomInteger[9, n], {n}] will not generate a packed array (see this as well), in contrast to the more orthodox RandomInteger[9, {n, n}]. Additionally, you might also wish to look at SparseArray[] objects with either sparse or dense diagonals.

POSTED BY: J. M.
Answer

Very interesting this information J.M.!

You are correct, I didn't even realize there was that kind of thing. These matrices (10 x 10):

p1

But when I use larger matrix like this one of 10000 x 10000, I believe Mathematica somehow automatically packed (??!):

p2

For this reason I believe that the result using the more orthodox form of RandomInteger[9,{n, n}], had the same performance specifically on this large matrix ( same tests using the form RandomInteger[9,{n, n}] ):

p3

  • Edited2:

One thing I noticed is that in the above tests, most of the results remained packed except Tr[a,List]:

p4

Or am I missing something? ... as this concept is still very new to me maybe I still do not understand completely.

These links you showed have a lot of information for me to study, I will try to make the most of them.

It also seems very interesting the command SparseArray[], will be my next tests.

I found this concept of packed very interesting! Thank you so much, I am learning a lot from this valuable information you are giving me.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract