>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Rel  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:
• Sparse literal and boxed arrays not yet implemented.