perlquestion
choroba
Spoiler alert: If you participate in [https://theweeklychallenge.org|The Weekly Challenge], don't read further if you haven't solved week 170 yet.<P>
Kronecker product is a matrix operation that uses elements of one matrix to multiply the second matrix. Mohammad shows this example:
<c>
A = [ 1 2 ]
[ 3 4 ]
B = [ 5 6 ]
[ 7 8 ]
A x B = [ 1 x [ 5 6 ] 2 x [ 5 6 ] ]
[ [ 7 8 ] [ 7 8 ] ]
[ 3 x [ 5 6 ] 4 x [ 5 6 ] ]
[ [ 7 8 ] [ 7 8 ] ]
= [ 1x5 1x6 2x5 2x6 ]
[ 1x7 1x8 2x7 2x8 ]
[ 3x5 3x6 4x5 4x6 ]
[ 3x7 3x8 4x7 4x8 ]
= [ 5 6 10 12 ]
[ 7 8 14 16 ]
[ 15 18 20 24 ]
[ 21 24 28 32 ]
</c><P>
When I saw matrices, I immediately thought [metamod://PDL]. After finding a solution, I tried searching for existing solutions, and found the following at [https://rosettacode.org/wiki/Kronecker_product#Perl|Rosetta Code]:<P>
<c>#!/usr/bin/perl
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
sub kron{
my $A = shift;
my $B = shift;
my ($r0, $c0) = $A->dims;
my ($r1, $c1) = $B->dims;
my $kron = zeroes($r0 * $r1, $c0 * $c1);
for(my $i = 0; $i < $r0; ++$i){
for(my $j = 0; $j < $c0; ++$j){
$kron(
($i * $r1) : (($i + 1) * $r1 - 1),
($j * $c1) : (($j + 1) * $c1 - 1)
) .= $A($i,$j) * $B;
}
}
return $kron;
}</c><P>
Wait, loops? The whole point of PDL is to hide loops. And indeed, my solution doesn't involve them. Also, a benchmark shows my solution is more than twice faster than the Rosetta Code one.<P>
I'm far from an expert on PDL or matrices in general. But it seems we can easily multiply each element in a matrix by the same number, but it's not so easy to multiply them by different numbers. But we can multiply each element by a matrix, so we just need to "inflate" the matrix, so instead of <P>
<c>
[ 1 2 ]
[ 3 4 ]
</c><P>
we'd have
<c>
[ 1 1 ] [ 2 2 ]
[ 1 1 ] [ 2 2 ]
[ 3 3 ] [ 4 4 ]
[ 3 3 ] [ 4 4 ]
</c><P>
That's what <c>dummy</c> does (two dummies, in fact, one in each dimension). Multiplying this with the second matrix gives us a result that has all the expected numbers, but a bit different dimensions.<P>
<c>
[ 5 6 ] [ 10 12 ]
[ 7 8 ] [ 14 16 ]
[ 15 18 ] [ 20 24 ]
[ 21 24 ] [ 28 32 ]
</c><P>
Fortunately, PDL has all the needed methods to reshuffle the submatrices into the expected result.<P>
<spoiler><c>
sub kronecker_product {
my ($x, $y) = @_;
my ($x0, $x1) = $x->dims;
my ($y0, $y1) = $y->dims;
return (
$y * $x->dummy(0, $y0)->dummy(1, $y1)
)->xchg(1, 2)->reshape($x0 * $y0, $x1 * $y1)
}
</c>
</spoiler><P>
It seems correct (it passes the test shown in the challenge and in the Wikipedia page), but my PDL is not so strong. Maybe it can be further improved?<P>
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-832495">
<c>map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]</c>
</div></div><!-- Wiki2Monks {"version":1.161} -->