>> << Ndx Usr Pri Phr Dic Rel Voc !: wd 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 or the`x` 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). `6$.y` gives the flag (the`flag` 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;flag` 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` .
`flag` | Various bit flags.

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^31` | 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 is the dimensions of 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 5, product 30, day 267,
     0  0  47 37 172 | 650782      the revenue was 128133
     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` (sparse in both dimensions);`<"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-03-25, the following facilities support sparse arrays:

    =       =.      =:
    < m     <.      <:
    >       >.      >:
    _       _.      _:

    +       +.      +:
    *       *.      *:
    -       -.      -:
    %       %. 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.
- The dyad`%.` only implements the case of triadiagonal matrices.
- Boxed left arguments for`|:` (diagonal slices) not yet implemented.
- The monads`f/` and`f/"r` are only implemented for`+ * >. <. +. *. = ~: ,` (and only boolean arguments for`=` and`~:`); on an axis of length 2, the monads`f/` and`f/"r` are implemented for any function.
- The monads`f/@,` (and`f/@:,` and`f/&,` and`f/&:,`)`` are supported by special code.
- `{` and`}` only accept the following index arguments: integer arrays,`<"1` on integer arrays, and scalar boxed indices (respectively, item indexing, scattered indexing, and index lists`a0;a1;a2;...`); and`` (`{` only) sparse arrays.

>> << Ndx Usr Pri Phr Dic Rel Voc !: wd Help Dictionary