Essays/Block Matrix Inverse

From J Wiki
Jump to: navigation, search

Block Matrix

A block matrix is a partition of the rows and columns of a matrix; in general, a block array is a partition of each dimension of the array. For example:

   ] xx=: i. 5 6
 0  1  2  3  4  5
 6  7  8  9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29

   ] yy=: (1 0 1 0 0 ; 1 0 0 1 1 0) <;.1 xx
┌────────┬──┬─────┐
│0 1 2   │3 │ 4  5│
│6 7 8   │9 │10 11│
├────────┼──┼─────┤
│12 13 14│15│16 17│
│18 19 20│21│22 23│
│24 25 26│27│28 29│
└────────┴──┴─────┘

As the example indicates, a block matrix can be created using the cut <;.1 with a left argument of boxed boolean vectors, with 1s marking the starts of partitions. (It can also be created using <;.2 with the 1s in the boolean vectors indicating the ends of the partitions.)

The rest of the essay will also use the following somewhat bigger example:

   x=: 5 7 6 8 ?.@$ 1e6
   p=: (i.&.>$x) e.&.> 0,&.>3 ?.@$&.>$x
   y=: p <;.1 x

   p
┌─────────┬─────────────┬───────────┬───────────────┐
│1 1 0 0 1│1 0 0 1 0 0 1│1 0 0 0 0 1│1 0 1 1 0 0 0 1│
└─────────┴─────────────┴───────────┴───────────────┘
   $y
3 3 2 4

Block Matrix Inverse

The inverse operation, obtaining a matrix from a block matrix (an array from a block array), can be effected by <;.1^:_1 or <;.2^:_1 , modelled as follows:

binv0=: 3 : 0
 z=. y
 for_r. (-i.) #$y do. z=. ,"r&.>/z end.
 > z
)

binv1=: [: > 3 : ',"(#$y)&.>/y'^:(#@$)

binv2=: 3 : 0
 r=. #$y
 c=. (\:"1 =i.r) <@(''&($,)"_1)@|:"_1 >&.|: $&.>y
 s=. +/&> c
 p=. (i.&.>s) e.&.> +/\@(0&,)&.> c
 s $ y /:&(;@:(,&.>)) p <;.1 i.s
)

binv0 and binv1 implement the following idea:

   t=: y
   t=: ,"4&.>/ t
   t=: ,"3&.>/ t
   t=: ,"2&.>/ t
   t=: ,"1&.>/ t
   x -: >t
1

   x -: binv0 y
1
   x -: binv1 y
1

binv2 is a step-by-step re-creation of the parts needed to create y from x in the first place. c are the partition lengths in each dimension. s is the shape of the original array. p are the partition vectors.

The values of the local names in binv2 when it is applied to y :

   r
4
   c
┌─────┬─────┬───┬───────┐
│1 3 1│3 3 1│5 1│2 1 4 1│
└─────┴─────┴───┴───────┘
   s
5 7 6 8
   p
┌─────────┬─────────────┬───────────┬───────────────┐
│1 1 0 0 1│1 0 0 1 0 0 1│1 0 0 0 0 1│1 0 1 1 0 0 0 1│
└─────────┴─────────────┴───────────┴───────────────┘

  x -: binv2 y
1

An Extension

The actual inverses of <;.1 and <;.2 permit the following extension: Each block may be a scalar or vector, which is reshaped to a diagonal array with the right shape.

bi=: 3 : 0
 ry=. #$y
 assert. 1 < ry
 assert. 32=3!:0 y
 d=. len y
 c=. >./"1&.> d
 assert. ; ,&.> c (= +. _1&=@])&.>d
 j=. I. , ry > #@$&> y
 t=. y j"_}~ (j{,{c) diag&.> j{,y
 > 3 : ',"(#$y)&.>/y'^:ry t
)

diag=: 4 : 0
 assert. (0=#$y) +. (<./x)=#y
 y ((#x) #&.> i.<./x)} x$0
)

len=: 3 : 0
 ry=. #$y
 r=. #&> s=. $&.> y
 assert. r e. 0 1,ry
 assert. ((-i.)ry) 4 : '*./,+./"x y'"0 _ *r
 (\:"1 =i.ry) <@,.@|:"_1 >&.|: (ry>r)}s,:<ry$_1
)

bi models the (extended) inverse of <;.1 and <;.2 . s diag y creates an array of shape s with scalar or vector y as the diagonal entries. len y computes the lengths of each block in each dimension.

Examples:

   4 4 diag 1
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
   3 3 5 diag 99 88 77
99  0  0 0 0
 0  0  0 0 0
 0  0  0 0 0

 0  0  0 0 0
 0 88  0 0 0
 0  0  0 0 0

 0  0  0 0 0
 0  0  0 0 0
 0  0 77 0 0

   yy
┌────────┬──┬─────┐
│0 1 2   │3 │ 4  5│
│6 7 8   │9 │10 11│
├────────┼──┼─────┤
│12 13 14│15│16 17│
│18 19 20│21│22 23│
│24 25 26│27│28 29│
└────────┴──┴─────┘
   len yy
┌─────┬───┐
│2 2 2│3 3│
│3 3 3│1 1│
│     │2 2│
└─────┴───┘
   <./"1&.> len yy
┌───┬─────┐
│2 3│3 1 2│
└───┴─────┘

   bi yy
 0  1  2  3  4  5
 6  7  8  9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29

   ] y1=: (<1) (<1 0)}yy
┌─────┬──┬─────┐
│0 1 2│3 │ 4  5│
│6 7 8│9 │10 11│
├─────┼──┼─────┤
│1    │15│16 17│
│     │21│22 23│
│     │27│28 29│
└─────┴──┴─────┘
   bi y1
0 1 2  3  4  5
6 7 8  9 10 11
1 0 0 15 16 17
0 1 0 21 22 23
0 0 1 27 28 29

   ] y2=: (<88 99) (<1 2)}yy
┌────────┬──┬─────┐
│0 1 2   │3 │ 4  5│
│6 7 8   │9 │10 11│
├────────┼──┼─────┤
│12 13 14│15│88 99│
│18 19 20│21│     │
│24 25 26│27│     │
└────────┴──┴─────┘
   bi y2
 0  1  2  3  4  5
 6  7  8  9 10 11
12 13 14 15 88  0
18 19 20 21  0 99
24 25 26 27  0  0



See also


Contributed by Roger Hui.