Mou Code

-- source -- -- Matrix Multiplication by PDC, Mou 1991 Algo.4.9 -- -- Definitions: -- N = 4 -- division: divide both A and B into quadrants, put them into all comb's, pick for use. d = sel (1,1,0,0, 0,0,1,1, 1,1,0,0, 0,0,1,1) @ outer @ ('d_lr^2', 'd_lr^2') -- combine: combine quadrants c = 'c_lr^2' -- sum block pairs hmm(p0,p1,p2,p3,p4,p5,p6,p7) = (p0 [+] p2, p1 [+] p3, p4 [+] p6, p5 [+] p7) -- base elements are 1x1. mm49 = PDC(d,c,id,hmm,AND @ (is1x1matrix,is1x1matrix),[*]) -- -- Application -- A = identity(N) B = randMat(N,N,[1,2,3,4,5,6,7,8,9], seed=42) trace(mm49, A, B) -- old -- A = randMatrix(N,N,fourth_roots(),seed=42) -- B = randMatrix(N,N,fourth_roots(),seed=43) -- end source -- -- trace: mm49([[1, 0, 0, 0] [[2, 1, 5, 4] [0, 1, 0, 0] [4, 3, 2, 9] [0, 0, 1, 0] [2, 7, 1, 1] [0, 0, 0, 1]] [2, 4, 4, 9]]) -- mm49([[1, 0, 0, 0] [[2, 1, 5, 4] [0, 1, 0, 0] [4, 3, 2, 9] [0, 0, 1, 0] [2, 7, 1, 1] [0, 0, 0, 1]] [2, 4, 4, 9]]) divide d -> ( ( [[1, 0] [[2, 1] [0, 1]] [4, 3]] ), ( [[1, 0] [[5, 4] [0, 1]] [2, 9]] ), ( [[0, 0] [[2, 7] [0, 0]] [2, 4]] ), ( [[0, 0] [[1, 1] [0, 0]] [4, 9]] ), ( [[0, 0] [[2, 1] [0, 0]] [4, 3]] ), ( [[0, 0] [[5, 4] [0, 0]] [2, 9]] ), ( [[1, 0] [[2, 7] [0, 1]] [2, 4]] ), ( [[1, 0] [[1, 1] [0, 1]] [4, 9]] ) ) mm49([[1, 0] [[2, 1] [0, 1]] [4, 3]]) divide d -> (( [[1]] [[2]] ), ( [[1]] [[1]] ), ( [[0]] [[4]] ), ( [[0]] [[3]] ), ( [[0]] [[2]] ), ( [[0]] [[1]] ), ( [[1]] [[4]] ), ( [[1]] [[3]] )) mm49([[1]] [[2]]) ⇣ atom; basef -> [[2]] mm49([[1]] [[1]]) ⇣ atom; basef -> [[1]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[3]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[1]]) ⇣ atom; basef -> [[0]] mm49([[1]] [[4]]) ⇣ atom; basef -> [[4]] mm49([[1]] [[3]]) ⇣ atom; basef -> [[3]] post hmm -> ( [[2]] [[1]] [[4]] [[3]] ) combine c_lr_sq -> [[2, 1] [4, 3]] mm49([[1, 0] [[5, 4] [0, 1]] [2, 9]]) divide d -> (( [[1]] [[5]] ), ( [[1]] [[4]] ), ( [[0]] [[2]] ), ( [[0]] [[9]] ), ( [[0]] [[5]] ), ( [[0]] [[4]] ), ( [[1]] [[2]] ), ( [[1]] [[9]] )) mm49([[1]] [[5]]) ⇣ atom; basef -> [[5]] mm49([[1]] [[4]]) ⇣ atom; basef -> [[4]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[9]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[5]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[1]] [[2]]) ⇣ atom; basef -> [[2]] mm49([[1]] [[9]]) ⇣ atom; basef -> [[9]] post hmm -> ( [[5]] [[4]] [[2]] [[9]] ) combine c_lr_sq -> [[5, 4] [2, 9]] mm49([[0, 0] [[2, 7] [0, 0]] [2, 4]]) divide d -> (( [[0]] [[2]] ), ( [[0]] [[7]] ), ( [[0]] [[2]] ), ( [[0]] [[4]] ), ( [[0]] [[2]] ), ( [[0]] [[7]] ), ( [[0]] [[2]] ), ( [[0]] [[4]] )) mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[7]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[7]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] post hmm -> ( [[0]] [[0]] [[0]] [[0]] ) combine c_lr_sq -> [[0, 0] [0, 0]] mm49([[0, 0] [[1, 1] [0, 0]] [4, 9]]) divide d -> (( [[0]] [[1]] ), ( [[0]] [[1]] ), ( [[0]] [[4]] ), ( [[0]] [[9]] ), ( [[0]] [[1]] ), ( [[0]] [[1]] ), ( [[0]] [[4]] ), ( [[0]] [[9]] )) mm49([[0]] [[1]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[1]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[9]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[1]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[1]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[9]]) ⇣ atom; basef -> [[0]] post hmm -> ( [[0]] [[0]] [[0]] [[0]] ) combine c_lr_sq -> [[0, 0] [0, 0]] mm49([[0, 0] [[2, 1] [0, 0]] [4, 3]]) divide d -> (( [[0]] [[2]] ), ( [[0]] [[1]] ), ( [[0]] [[4]] ), ( [[0]] [[3]] ), ( [[0]] [[2]] ), ( [[0]] [[1]] ), ( [[0]] [[4]] ), ( [[0]] [[3]] )) mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[1]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[3]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[1]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[3]]) ⇣ atom; basef -> [[0]] post hmm -> ( [[0]] [[0]] [[0]] [[0]] ) combine c_lr_sq -> [[0, 0] [0, 0]] mm49([[0, 0] [[5, 4] [0, 0]] [2, 9]]) divide d -> (( [[0]] [[5]] ), ( [[0]] [[4]] ), ( [[0]] [[2]] ), ( [[0]] [[9]] ), ( [[0]] [[5]] ), ( [[0]] [[4]] ), ( [[0]] [[2]] ), ( [[0]] [[9]] )) mm49([[0]] [[5]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[9]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[5]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[9]]) ⇣ atom; basef -> [[0]] post hmm -> ( [[0]] [[0]] [[0]] [[0]] ) combine c_lr_sq -> [[0, 0] [0, 0]] mm49([[1, 0] [[2, 7] [0, 1]] [2, 4]]) divide d -> (( [[1]] [[2]] ), ( [[1]] [[7]] ), ( [[0]] [[2]] ), ( [[0]] [[4]] ), ( [[0]] [[2]] ), ( [[0]] [[7]] ), ( [[1]] [[2]] ), ( [[1]] [[4]] )) mm49([[1]] [[2]]) ⇣ atom; basef -> [[2]] mm49([[1]] [[7]]) ⇣ atom; basef -> [[7]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[2]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[7]]) ⇣ atom; basef -> [[0]] mm49([[1]] [[2]]) ⇣ atom; basef -> [[2]] mm49([[1]] [[4]]) ⇣ atom; basef -> [[4]] post hmm -> ( [[2]] [[7]] [[2]] [[4]] ) combine c_lr_sq -> [[2, 7] [2, 4]] mm49([[1, 0] [[1, 1] [0, 1]] [4, 9]]) divide d -> (( [[1]] [[1]] ), ( [[1]] [[1]] ), ( [[0]] [[4]] ), ( [[0]] [[9]] ), ( [[0]] [[1]] ), ( [[0]] [[1]] ), ( [[1]] [[4]] ), ( [[1]] [[9]] )) mm49([[1]] [[1]]) ⇣ atom; basef -> [[1]] mm49([[1]] [[1]]) ⇣ atom; basef -> [[1]] mm49([[0]] [[4]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[9]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[1]]) ⇣ atom; basef -> [[0]] mm49([[0]] [[1]]) ⇣ atom; basef -> [[0]] mm49([[1]] [[4]]) ⇣ atom; basef -> [[4]] mm49([[1]] [[9]]) ⇣ atom; basef -> [[9]] post hmm -> ( [[1]] [[1]] [[4]] [[9]] ) combine c_lr_sq -> [[1, 1] [4, 9]] post hmm -> ( [[2, 1] [[5, 4] [[2, 7] [[1, 1] [4, 3]] [2, 9]] [2, 4]] [4, 9]] ) combine c_lr_sq -> [[2, 1, 5, 4] [4, 3, 2, 9] [2, 7, 1, 1] [2, 4, 4, 9]] -- result: [[2, 1, 5, 4] [4, 3, 2, 9] [2, 7, 1, 1] [2, 4, 4, 9]] --