Kronecker product: Difference between revisions

Content added Content deleted

Inline

Revision as of 11:26, 5 April 2017

This page uses content from Wikipedia. The original article was at Kronecker product. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

Task

Implement the Kronecker product of two matrices (arbitrary sized) resulting in a block matrix.

Test cases

Show results for each of the following 2 samples:

Sample 1 (from Wikipedia):

|1 2|  x  |0 5|	= | 0  5  0 10|
|3 4|     |6 7|	  | 6  7 12 14|
		  | 0 15  0 20|
		  |18 21 24 28|

Sample 2:

|0 1 0| x |1 1 1 1| = |0 0 0 0 1 1 1 1 0 0 0 0|
|1 1 1|   |1 0 0 1|   |0 0 0 0 1 0 0 1 0 0 0 0|
|0 1 0|   |1 1 1 1|   |0 0 0 0 1 1 1 1 0 0 0 0|
	              |1 1 1 1 1 1 1 1 1 1 1 1|
                      |1 0 0 1 1 0 0 1 1 0 0 1|
                      |1 1 1 1 1 1 1 1 1 1 1 1|
                      |0 0 0 0 1 1 1 1 0 0 0 0|
                      |0 0 0 0 1 0 0 1 0 0 0 0|
                      |0 0 0 0 1 1 1 1 0 0 0 0|

See implementations and results below in JavaScript and PARI/GP languages.

Haskell

<lang haskell>import Data.List (transpose)

kprod

 :: Num a
 => a -> a -> a

kprod xs ys =

 let f = (<$>) . (<$>) . (*)
 in concat $ ((concat <$>) . transpose) <$> ((<$>) (`f` ys) <$> xs)

main :: IO () main = do

 mapM_ print $ kprod [[1, 2], [3, 4]] [[0, 5], [6, 7]]
 putStrLn []
 mapM_ print $
   kprod
     [[0, 1, 0], [1, 1, 1], [0, 1, 0]]
     [[1, 1, 1, 1], [1, 0, 0, 1], [1, 1, 1, 1]]</lang>

Output:

[0,5,0,10]
[6,7,12,14]
[0,15,0,20]
[18,21,24,28]

[0,0,0,0,1,1,1,1,0,0,0,0]
[0,0,0,0,1,0,0,1,0,0,0,0]
[0,0,0,0,1,1,1,1,0,0,0,0]
[1,1,1,1,1,1,1,1,1,1,1,1]
[1,0,0,1,1,0,0,1,1,0,0,1]
[1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,1,1,1,1,0,0,0,0]
[0,0,0,0,1,0,0,1,0,0,0,0]
[0,0,0,0,1,1,1,1,0,0,0,0]

JavaScript

Imperative

Version #1.

Works with: Chrome

<lang javascript> // matkronprod.js // Prime function: // mkp arrow function: Return the Kronecker product of the a and b matrices. // Note: both a and b must be matrices, i.e., 2D rectangular arrays. mkp=(a,b)=>a.map(a=>b.map(b=>a.map(y=>b.map(x=>r.push(y*x)),t.push(r=[]))),t=[])&&t; // Helper functions: // Log title and matrix mat to console function matl2cons(title,mat) {console.log(title); console.log(mat.join`\n`)} // Print title to document function pttl2doc(title) {document.write(''+title+'
')} // Print title and matrix mat to document function matp2doc(title,mat) {

 document.write(''+title+':
');
 for (var i = 0; i < mat.length; i++) {
   document.write('  '+mat[i].join(' ')+'
');
 }

} </lang>

Required tests

 <title>Kronecker product: Sample 1 (from Wikipedia) and Sample 2</title>
 <script src="matkronprod.js"></script>
 <script>
 var mr,ttl='Kronecker product of A and B matrices';
 [ {a:[[1,2],[3,4]],b:[[0,5],[6,7]] },
   {a:[[0,1,0],[1,1,1],[0,1,0]],b:[[1,1,1,1],[1,0,0,1],[1,1,1,1]] }
 ].forEach(m=>{
   console.log(ttl); pttl2doc(ttl);
   matl2cons('A',m.a); matp2doc('A',m.a);
   matl2cons('B',m.b); matp2doc('B',m.b);
   mr=mkp(m.a,m.b);
   matl2cons('A x B',mr); matp2doc('A x B',mr);
   })
 </script>

</head><body></body> </html> </lang>

Output:

Console and page results

Kronecker product of A and B matrices
A
1,2
3,4
B
0,5
6,7
A x B
0,5,0,10
6,7,12,14
0,15,0,20
18,21,24,28
Kronecker product of A and B matrices
A
0,1,0
1,1,1
0,1,0
B
1,1,1,1
1,0,0,1
1,1,1,1
A x B
0,0,0,0,1,1,1,1,0,0,0,0
0,0,0,0,1,0,0,1,0,0,0,0
0,0,0,0,1,1,1,1,0,0,0,0
1,1,1,1,1,1,1,1,1,1,1,1
1,0,0,1,1,0,0,1,1,0,0,1
1,1,1,1,1,1,1,1,1,1,1,1
0,0,0,0,1,1,1,1,0,0,0,0
0,0,0,0,1,0,0,1,0,0,0,0
0,0,0,0,1,1,1,1,0,0,0,0

Version #2.

This version is more understandable for sure.

Translation of: PARI/GP

Works with: Chrome

<lang javascript> // matkronprod2.js // Prime function: // mkp2(): Return the Kronecker product of the a and b matrices // Note: both a and b must be matrices, i.e., 2D rectangular arrays. function mkp2(a,b) {

 var m=a.length, n=a[0].length, p=b.length, q=b[0].length;
 var rtn=m*p, ctn=n*q; var r=new Array(rtn);
 for (var i=0; i<rtn; i++) {r[i]=new Array(ctn)
   for (var j=0;j<ctn;j++) {r[i][j]=0}
 }
 for (var i=0; i<m; i++) {
   for (var j=0; j<n; j++) {
     for (var k=0; k<p; k++) {
       for (var l=0; l<q; l++) {
         r[p*i+k][q*j+l]=a[i][j]*b[k][l];
       }}}}//all4forend
 return(r);

} // Helper functions: // Log title and matrix mat to console function matl2cons(title,mat) {console.log(title); console.log(mat.join`\n`)} // Print title to document function pttl2doc(title) {document.write(''+title+'
')} // Print title and matrix mat to document function matp2doc(title,mat) {

 document.write(''+title+':
');
 for (var i=0; i < mat.length; i++) {
   document.write('  '+mat[i].join(' ')+'
');
 }

} </lang>

Required tests

 <title>Kronecker product v.2: Sample 1 (from Wikipedia) and Sample 2</title>
 <script src="matkronprod2.js"></script>
 <script>
 var mr,ttl='Kronecker product of A and B matrices';
 [ {a:[[1,2],[3,4]],b:[[0,5],[6,7]] },
   {a:[[0,1,0],[1,1,1],[0,1,0]],b:[[1,1,1,1],[1,0,0,1],[1,1,1,1]] }
 ].forEach(m=>{
   console.log(ttl); pttl2doc(ttl);
   matl2cons('A',m.a); matp2doc('A',m.a);
   matl2cons('B',m.b); matp2doc('B',m.b);
   mr=mkp2(m.a,m.b);
   matl2cons('A x B',mr); matp2doc('A x B',mr);
   })
 </script>

</head><body></body> </html> </lang>

Output:

Console and page results

Output is identical to Version #1 above.

Functional

ES6

Translation of: Haskell

(As JavaScript is now widely embedded in non-browser contexts, a non-HTML string value is returned here) <lang javascript>(() => {

   'use strict';

   // GENERIC FUNCTIONS ------------------------------------------------------

   // concat :: a -> [a]
   const concat = xs => [].concat.apply([], xs);

   // show :: a -> String
   const show = x => JSON.stringify(x); //, null, 2);

   // transpose :: a -> a
   const transpose = xs =>
       xs[0].map((_, col) => xs.map(row => row[col]));

   // unlines :: [String] -> String
   const unlines = xs => xs.join('\n');

   // KRONECKER PRODUCT OF TWO MATRICES --------------------------------------

   // kprod :: Num -> Num -> Num
   const kprod = (xs, ys) =>
       concat(xs.map(row => row.map(x => f(x, ys)))
           .map(m => transpose(m)
               .map(concat)));

   // (* n) mapped over each element in a matrix
   // f :: Num -> Num -> Num
   const f = (n, mx) => mx.map(row => row.map(x => x * n));

   // TEST -------------------------------------------------------------------
   return unlines([
       kprod([
           [1, 2],
           [3, 4]
       ], [
           [0, 5],
           [6, 7]
       ]),
       [], // One empty output line
       kprod([
           [0, 1, 0],
           [1, 1, 1],
           [0, 1, 0]
       ], [
           [1, 1, 1, 1],
           [1, 0, 0, 1],
           [1, 1, 1, 1]
       ])
   ].map(rows => unlines(rows.map(show))));

})();</lang>

Output:

[0,5,0,10]
[6,7,12,14]
[0,15,0,20]
[18,21,24,28]

[0,0,0,0,1,1,1,1,0,0,0,0]
[0,0,0,0,1,0,0,1,0,0,0,0]
[0,0,0,0,1,1,1,1,0,0,0,0]
[1,1,1,1,1,1,1,1,1,1,1,1]
[1,0,0,1,1,0,0,1,1,0,0,1]
[1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,1,1,1,1,0,0,0,0]
[0,0,0,0,1,0,0,1,0,0,0,0]
[0,0,0,0,1,1,1,1,0,0,0,0]

PARI/GP

Works with: PARI/GP version 2.9.1 and above

<lang parigp> \\ Print title and matrix mat rows. 4/17/16 aev matprows(title,mat)={print(title); for(i=1,#mat[,1], print(mat[i,]))} \\ \\ Create and return the Kronecker product of the a and b matrices. 4/17/16 aev matkronprod(a,b,pflg=0)={ my(m=#a[,1],n=#a[1,],p=#b[,1],q=#b[1,],r,rtn,ctn); rtn=m*p; ctn=n*q; if(pflg,print(" *** Kronecker product - a: ",m," x ",n," b: ",p," x ",q," result r: ",rtn," x ",ctn)); r=matrix(rtn,ctn); for(i=1,m, for(j=1,n, for(k=1,p, for(l=1,q,

   r[p*(i-1)+k,q*(j-1)+l]=a[i,j]*b[k,l];

))));\\all4fend if(pflg,print(r)); return(r); } {\\ Requireq tests: my(a,b,r); \\ Sample 1 a=[1,2;3,4]; b=[0,5;6,7]; r=matkronprod(a,b); matprows("Sample 1 result:",r); \\ Sample 2 a=[0,1,0;1,1,1;0,1,0]; b=[1,1,1,1;1,0,0,1;1,1,1,1]; r=matkronprod(a,b); matprows("Sample 2 result:",r); } </lang>

Output:

Sample 1 result:
[0, 5, 0, 10]
[6, 7, 12, 14]
[0, 15, 0, 20]
[18, 21, 24, 28]
Sample 2 result:
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]