>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Voc  !:  Help  Dictionary

Sparse $.  _ _ _ Sparse

$.y converts a dense array to sparse, and conversely $.^:_1 y converts a sparse array to dense.

The identities f -: f&.$. and f -: f&.($.^:_1) hold for any function f , with the possible exception of those (like overtake {.) which use the sparse element as the fill.
 		   0$.y applies $. or $.^:_1 as appropriate; that is, converts a dense array to sparse and a sparse array to dense.

1$.sh;a;e produces a sparse array. sh specifies the shape. a specifies the sparse axes; negative indexing may be used. e specifies the “zero” element, and its type determines the type of the array. The argument may also be sh;a (e is assumed to be a floating point 0) or just sh (a is assumed to be i.#sh — all axes are sparse — and e a floating point 0).

2$.y gives the sparse axes (the a part);
(2;a)$.y (re-)specifies the sparse axes;
(2 1;a)$.y gives the number of bytes required for (2;a)$.y ;
(2 2;a)$.y gives the number of items in the i part for the specified sparse axes a (that is, #4$.(2;a)$.y ).

3$.y gives the sparse element (the e part); (3;e)$.y respecifies the sparse element.

4$.y gives the index matrix (the i part).

5$.y gives the value array (the x part).

7$.y gives the number of non-sparse entries in array y; that is, #4$.y or #5$.y.

8$.y removes any completely “zero” value cells and the corresponding rows in the index matrix.

The inverse of n&$. is (-n)&$. .
 

The remainder of this text is divided into the following sections: Introduction, Representation, Assertions, Further Examples, Sparse Linear Algebra, and Implementation Status.

Introduction

We describe a sparse array extension to J using a representation that “does not store zeros”. One new verb $. is defined to create and manipulate sparse arrays, and existing primitives are extended to operate on such arrays. These ideas are illustrated in following examples:

   ] d=: (?. 3 4$2) * ?. 3 4$100
0 55 79  0
0 39  0 57
0  0  0  0

   ] s=: $. d                  convert d to sparse and assign to s
0 1 | 55
0 2 | 79                       the display of s gives the indices of the
1 1 | 39                       “non-zero” cells and the corresponding values
1 3 | 57

   d -: s                      d and s match
1

   o. s                        π times s
0 1 | 172.788
0 2 | 248.186
1 1 | 122.522
1 3 | 179.071

   o. d                        π times d
0 172.788 248.186       0
0 122.522       0 179.071
0       0       0       0

   (o. s) -: o. d              function results independent of representation
1

   0.5 + o. s
0 1 | 173.288
0 2 | 248.686
1 1 | 123.022
1 3 | 179.571

   <. 0.5 + o. s
0 1 | 173
0 2 | 248
1 1 | 123
1 3 | 179

   (<. 0.5 + o. s) -: <. 0.5 + o. d
1

   d + s                       function arguments can be dense or sparse
0 1 | 110
0 2 | 158
1 1 |  78
1 3 | 114

   (d + s) -: 2*s              familiar algebraic properties are preserved
1

   (d + s) -: 2*d
1

   +/ s
1 | 94
2 | 79
3 | 57
   
   +/"1 s
0 | 134
1 |  96

   |. s                        reverse
1 1 | 39
1 3 | 57
2 1 | 55
2 2 | 79

   |."1 s
0 1 | 79
0 2 | 55
1 0 | 57
1 2 | 39

   |: s                        transpose
1 0 | 55
1 1 | 39
2 0 | 79
3 1 | 57

   $ |: s
4 3

   $.^:_1 |: s                 $.^:_1 converts a sparse array to dense
 0  0 0
55 39 0
79  0 0
 0 57 0

   (|:s) -: |:d
1

   , s                         ravel; a sparse vector
1 | 55
2 | 79
5 | 39
7 | 57

   $ , s
12
Representation

A sparse array y may be boolean, integer, floating point, complex, literal, or boxed, and has the (internal) parts sh;a;e;i;x where:

sh  Shape, $y . Elements of the shape must be less than 2^31 , but the product over the shape may be larger than 2^31 .
a  Axe(s), a vector of the sorted sparse (indexed) axes.
e  Sparse element (“zero”). e is also used as the fill in any overtake of the array.
i  Indices, an integer matrix of indices for the sparse axes.
x  Values, a (dense) array of usually non-zero cells for the non-sparse axes corresponding to the index matrix i .

For the sparse matrix s used in the introduction,
   ] d=: (?. 3 4$2) * ?. 3 4$100
0 55 79  0
0 39  0 57
0  0  0  0
    
   ] s=: $. d
0 1 | 55
0 2 | 79
1 1 | 39
1 3 | 57
The shape is 3 4 ; the sparse axes are 0 1 ; the sparse element is 0; the indices are the first two columns of numbers in the display of s ; and the values are the last column.

Scalars continue to be represented as before (densely). All primitives accept sparse or dense arrays as arguments (e.g. sparse+dense or sparse$sparse). The display of a sparse array is a display of the index matrix (the i part), a blank column, a column of vertical lines, another blank column, and the corresponding value cells (the x part).

Letting the sparse element be variable rather than fixed at zero makes many more functions closed on sparse arrays (e.g. ^y or 10+y), and familiar results can be produced by familiar phrases (e.g. <.0.5+y for rounding to the nearest integer).

Assertions

The following assertions hold for a sparse array, and displaying a sparse array invokes these consistency checks on it.

imax =: _1+2^IF64{31 63 the largest internal integer
rank =: #@$ rank
type =: 3!:0 internal type
 
1 = rank sh vector
sh -: <. sh integral
imax >: #sh at most imax elements
(0<:sh) *. (sh<:imax) bounded by 0 and imax
 
1 = rank a vector
a e. i.#sh bounded by 0 and rank-1
a -: ~. a elements are unique
a -: /:~ a sorted
 
0 = rank e atomic
(type e) = type x has the same internal type as x
 
2 = rank i matrix
4 = type i integral
(#i) = #x as many rows as the number of items in x
({:$i) = #a as many columns as there are sparse axes
(#i) <: */a{sh # rows bounded by product over sparse axes lengths
imax >: */$i # elements is bounded by imax
(0<:i) *. (i <"1 a{sh) i bounded by 0 and the lengths of the sparse axes
i -: ~.i rows are unique
i -: /:~ i rows are sorted
 
(rank x) = 1+(#sh)-#a rank equals 1 plus the number of dense axes
imax >: */$x # elements is bounded by imax
(}.$x)-:((i.#sh)-.a){s item shape are elements of the shape corresponding to the dense axes
(type x) e. 1 2 4 8 16 32  internal type is boolean, character, integer, real, complex, or boxed

Further Examples

   ] d=: (0=?. 2 3 4$3) * ?. 2 3 4$100
46  0  0  0
 0 39  0  0
 0  0 46  0

 0  0  0  0
 0 60  0 62
 0  0 60 64

   ] s=: $. d                  convert d to sparse and assign to s
0 0 0 | 46
0 1 1 | 39
0 2 2 | 46
1 1 1 | 60
1 1 3 | 62
1 2 2 | 60
1 2 3 | 64

   d -: s                      match is independent of representation
1

   2 $. s                      sparse axes
0 1 2

   3 $. s                      sparse element
0

   4 $. s                      index matrix; columns correspond to the sparse axes
0 0 0
0 1 1
0 2 2
1 1 1
1 1 3
1 2 2
1 2 3

   5 $. s                      corresponding values
46 39 46 60 62 60 64

   ] u=: (2;2)$.s              make 2 be the sparse axis
0 | 46  0  0
  |  0  0  0
  |         
1 |  0 39  0
  |  0 60  0
  |         
2 |  0  0 46
  |  0  0 60
  |         
3 |  0  0  0
  |  0 62 64

   4 $. u                      index matrix
0
1
2
3

   5 $. u                      corresponding values
46  0  0
 0  0  0

 0 39  0
 0 60  0

 0  0 46
 0  0 60

 0  0  0
 0 62 64

   ] t=: (2;0 1)$.s            make 0 1 be the sparse axes
0 0 | 46  0  0  0
0 1 |  0 39  0  0
0 2 |  0  0 46  0
1 1 |  0 60  0 62
1 2 |  0  0 60 64

   7 {. t                      take
0 0 | 46  0  0  0
0 1 |  0 39  0  0
0 2 |  0  0 46  0
1 1 |  0 60  0 62
1 2 |  0  0 60 64

   $ 7 {. t
7 3 4

   7{."1 t                     take with rank
0 0 | 46  0  0  0 0 0 0
0 1 |  0 39  0  0 0 0 0
0 2 |  0  0 46  0 0 0 0
1 1 |  0 60  0 62 0 0 0
1 2 |  0  0 60 64 0 0 0

   0 = t
0 0 | 0 1 1 1
0 1 | 1 0 1 1
0 2 | 1 1 0 1
1 1 | 1 0 1 0
1 2 | 1 1 0 0

   3 $. 0 = t                  the sparse element of 0=t is 1
1

   +/ , 0 = t
17

   +/ , 0 = d                  answers are independent of representation
17

   0 { t                       from
0 | 46  0  0 0
1 |  0 39  0 0
2 |  0  0 46 0

   _2 (<1 2 3)}t               amend
0 0 | 46  0  0  0
0 1 |  0 39  0  0
0 2 |  0  0 46  0
1 1 |  0 60  0 62
1 2 |  0  0 60 _2

   s=: 1 $. 20 50 1000 75 366
   $ s                         20 countries, 50 regions, 1000 salespersons,
20 50 1000 75 366              75 products, 366 days in a year

   */ $ s                      the product over the shape can be greater than 2^31
2.745e10

   r=: ?. 1e5 $ 1e6            revenues
   i=: ?. 1e5 5 $ $ s          corresponding locations
   s=: r (<"1 i)} s            assign revenues to corresponding locations

   7 {. ": s                   the first 7 rows in the display of s
 0  0  20 48 150 | 395543      the first row says that for country 0, region 0,
 0  0  39 40  67 | 316198      salesperson 20, product 48, day 150,
 0  0  47 37 172 | 650782      the revenue was 395543
 0  0  52 32 358 | 789844
 0  0  54 62  82 | 923413
 0  0  67 17 103 | 567367
 0  0  91 13 295 | 470919


   +/ , s                      total revenue
|limit error                   the expression failed on ,s because it would
| +/    ,s                     have required a vector of length 2.745e10

   +/@, s                      total revenue
4.98338e10                     f/@, is supported by special code

   +/+/+/+/+/ s                total revenue
4.98338e10

   +/^:5 s
4.98338e10

   +/^:_ s
4.98338e10

   +/ r
4.98338e10

   +/"1^:4 s                   total revenue by country
 0 | 2.49298e9
 1 | 2.35118e9
 2 | 2.49324e9
 3 | 2.44974e9
 4 | 2.45138e9
 5 | 2.47689e9
 6 | 2.55936e9
 7 | 2.47153e9
 8 | 2.45907e9
 9 | 2.50249e9
10 | 2.52785e9
11 | 2.49482e9
12 | 2.57532e9
13 | 2.46509e9
14 | 2.54962e9
15 | 2.48942e9
16 | 2.50503e9
17 | 2.52147e9
18 | 2.50127e9
19 | 2.49603e9

   t=: +/^:2 +/"1^:2 s         total revenue by salesperson

   $t
1000

   7{.t
0 | 5.08254e7
1 | 5.61577e7
2 | 4.19914e7
3 | 5.90514e7
4 | 6.08208e7
5 | 4.10632e7
6 | 4.36616e7
Sparse Linear Algebra

Currently, only sparse matrix multiplication and the solutions of tri-diagonal linear system are implemented. For example:
   f=: }. @ }: @ (,/) @ (,."_1 +/&_1 0 1) @ i.

   f 5                         indices for a 5 by 5 tri-diagonal matrix
0 0
0 1
1 0
1 1
1 2
2 1
2 2
2 3
3 2
3 3
3 4
4 3
4 4

   s=: (?. 13$100) (<"1 f 5)} 1 $. 5 5;0 1
   $s
5 5
The phrase 1$.5 5;0 1 makes a sparse array with shape 5 5 and sparse axes 0 1 ; <"1 f 5 makes boxed indices; and x (<"1 f 5)}y amends by x the locations in y indicated by the indices (scattered amendment).
   s
0 0 | 46
0 1 | 55
1 0 | 79
1 1 | 52
1 2 | 54
2 1 | 39
2 2 | 60
2 3 | 57
3 2 | 60
3 3 | 94
3 4 | 46
4 3 | 78
4 4 | 13

   ] d=: $.^:_1 s              the dense representation of s
46 55  0  0  0
79 52 54  0  0
 0 39 60 57  0
 0  0 60 94 46
 0  0  0 78 13

   ] y=: ?. 5$80
66 75 79 52 54

   y %. s
0.352267 0.905377 0.00169115 0.764716 _0.434452

   y %. d                      answers are independent of representation
0.352267 0.905377 0.00169115 0.764716 _0.434452

   s=: (?. (_2+3*1e5)$1000) (<"1 f 1e5)} 1 $. 1e5 1e5;0 1

   $ s                         s is a 1e5 by 1e5 matrix
100000 100000

   y=: ?. 1e5$1000

   ts=: 6!:2 , 7!:2@]          time and space for execution

   ts 'y %. s'
0.0550291 5.24358e6            0.056 seconds; 5.2 megabytes (Pentium III 500 Mhz)
Implementation Status

As of 2005-12-17, the following facilities support sparse arrays:

=       =.      =: 
< d     <.      <: 
>       >.      >: 
_       _.      _:

+       +.      +:
*       *.      *:
-       -.      -:
%       %. d    %:

^       ^.
$       $.      $:
~       ~.      ~:
|       |.      |:

        ..      .:
:       :.      ::
,       ,.      ,:
        ;.

#
!       !.      !:
/ m     /. d    /: m
\ m     \. m    \: m

[               [:
]         
{ d     {.      {:
} d     }.      }:

"       ".      ": m
`               `:
@       @.      @:
&       &.      &:

e. d
i.
i:
j.
o.
r.
_9: to 9:

3!:0 
3!:1
3!:2
3!:3
4!:55
Notes:

>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Voc  !:  Help  Dictionary