Outer Product

From APL Wiki
Jump to navigation Jump to search

Outer Product (∘.), or Table is a monadic operator, which will produce a dyadic function when applied with a dyadic function. Outer product applies the operand function on each element of the left array with each element of the right array. It can be described as a shortcut for constructing nested for loops, and as a generalization of the Cartesian product to operations other than catenation.

Syntax

Outer Product differs from all other monadic operators, which are written as a single glyph, with the operand on the left. For historical reasons, the outer product operator is a bi-glyph denoted as ∘., and its operand appears on the right. This special notation is derived from the f.g notation of inner product:[1]

The result of an inner product is an array with rank two less than the sum of the argument ranks. The result of an outer product, on the other hand, is always an array of rank equal to the sum of the argument ranks. This follows from the fact that the reduction operation, which collapses two dimensions in an inner product, is not used in the outer product. The notation for outer product reflects this by canonically using a small circle as the first symbol. Thus, the ordinary outer product is written as a∘.×b .

This syntactical inconsistency is resolved in J and BQN, where the outer product operator, called Table, and denoted / and ⌜ respectively, has the usual operator syntax.

Model

Outer Product can be modeled as f¨⍤0 99.

Examples

      x ← 1 2 3
      y ← 4 5 6
      x ∘., y ⍝ visualizing outer product
┌───┬───┬───┐
│1 4│1 5│1 6│
├───┼───┼───┤
│2 4│2 5│2 6│
├───┼───┼───┤
│3 4│3 5│3 6│
└───┴───┴───┘

      ⍝ works for multi-dimensional arrays as well
      y←2 3 ⍴ 'abcdef'
      x←2 2 ⍴ ⍳4
      x∘.,y 
┌───┬───┬───┐
│1 a│1 b│1 c│
├───┼───┼───┤
│1 d│1 e│1 f│
└───┴───┴───┘
┌───┬───┬───┐
│2 a│2 b│2 c│
├───┼───┼───┤
│2 d│2 e│2 f│
└───┴───┴───┘
             
┌───┬───┬───┐
│3 a│3 b│3 c│
├───┼───┼───┤
│3 d│3 e│3 f│
└───┴───┴───┘
┌───┬───┬───┐
│4 a│4 b│4 c│
├───┼───┼───┤
│4 d│4 e│4 f│
└───┴───┴───┘

Applications

Outer product is useful for solving problems that intuitively require a polynomial time algorithm. This may also indicate that such an algorithm is not the fastest solution.

For example, suppose we want to find duplicated elements in an non-nested array. Intuitively speaking, the easiest way to solve this problem is to compare each element of the array with all other elements, which is exactly what an outer product does. 

      x ← 1 2 3 2
      ⎕ ← matrix ← x∘.=x ⍝ compare elements with each other using equal
1 0 0 0
0 1 0 1
0 0 1 0
0 1 0 1
      ⎕ ← count ← +/matrix ⍝ get the number of occurence of each element
1 2 1 2
      ⎕ ← indices ← count ≥ 2 ⍝ get the indices of elements which occured more than once
0 1 0 1
      ⎕ ← duplicated ← ∪ indices/x 
2

      ∪((+/x∘.=x)≥2)/x ⍝ everything above in one line
2
      (⊢∪⍤/⍨2≤(+/∘.=⍨)) x ⍝ point-free/tacit version
2

Using similar techniques, we can define a function that generates prime numbers by using an outer product of Residue. 

     primes ← {x←1↓⍳⍵ ⋄ (2>+⌿0=x∘.|x)/x}
     primes 10
2 3 5 7
      primes 20
2 3 5 7 11 13 17 19

Here there are faster solutions such as the Sieve of Eratosthenes.

Differences between dialects

J's Table differs from APL's Outer Product by enabling Cartesian pairing between cells of ranks other than 0, and between cells of different rank for the left vs. right arguments, without needing to first enclose the relevant cells. It is defined as u"(lu, _), where lu is the left rank of operand u (_ denotes infinity in J). The results of the individual applications of u are collectively framed by the catenation of the frames of the left and right arguments relative to their lu- and ru-cells respectively, where lu and ru are the dyadic ranks of the operand u. Unlike APL's Outer Product, J's Table does not use an implicit Each, so the results of the individual applications of its operand are not boxed (unless the given operand itself does so). 

   NB. Cartesian pairing of rows
   x=: 100+i.2 2
   y=: i.3 4
   x ,"1/ y       NB. same as x ,"1"1 _ y
100 101 0 1  2  3
100 101 4 5  6  7
100 101 8 9 10 11

102 103 0 1  2  3
102 103 4 5  6  7
102 103 8 9 10 11

   NB. Cartesian pairing of x-matrices and y-cubes
   x=: 100+i.2 2 2
   y=: i.2 2 2 4
   x ;"2 3/ y     NB. same as x ;"2 3"2 _ y
┌───────┬───────────┐
│100 101│ 0  1  2  3│
│102 103│ 4  5  6  7│
│       │           │
│       │ 8  9 10 11│
│       │12 13 14 15│
├───────┼───────────┤
│100 101│16 17 18 19│
│102 103│20 21 22 23│
│       │           │
│       │24 25 26 27│
│       │28 29 30 31│
└───────┴───────────┘

┌───────┬───────────┐
│104 105│ 0  1  2  3│
│106 107│ 4  5  6  7│
│       │           │
│       │ 8  9 10 11│
│       │12 13 14 15│
├───────┼───────────┤
│104 105│16 17 18 19│
│106 107│20 21 22 23│
│       │           │
│       │24 25 26 27│
│       │28 29 30 31│
└───────┴───────────┘
Works in: J

In APL one can accomplish this behavior by enclosing the relevant cells of each argument before applying the outer product operation (or by successive applications of Rank, e.g. f⍤2 99⍤99 1). Conversely, the behavior of APL's Outer Product can be accomplished in terms of J's Table by adding the Each modifier, as in u&.>/ or u&>/, depending on whether the given operand is a scalar function.

The Cartesian pairing behavior of J's Table results from each "(lu, _) cell-pairing being processed by u, which applies its own ranks to divide up the right argument into cells.

However, it does not allow for creating a Cartesian pairing involving cells of the left argument specified with negative left rank L (except trivially, in cases in which Table's application has no effect, e.g. u"2 _"_ 1/). This is because negative assigned rank in J is encoded as infinite rank; in J's terminology, negative rank is "internal rank" only. 

   +b.0
0 0 0
   }.+"_1 _2 b.0  NB. the dyadic ranks of derived verb +"_1 _2 as seen by Table
_ _

Given the u"(lu, _) definition of Table, even in a hypothetical J dialect in which assignment of negative rank is visible as such to modifiers, a left negative rank L used with Table would be applied twice (once by the ranks added by Table, and once by the operand itself). This would result in the L-cells of each of the left argument's L-cells being paired 1-to-1 with the specified cells of the right argument—not a Cartesian pairing. If a J dialect both allowed externally visible negative rank and defined Table to instead be u"lu _"_ ru, one could express e.g. the Cartesian pairing of the major cells of the left and right arguments as u"_1/.

External links

Documentation

References

  1. ↑ Falkoff, A.D. and K.E. Iverson. The APL\360 Terminal System: Inner and Outer Products. Research Report RC-1922. IBM Watson Research Center. 1967-10-16.
APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic Conjugate ∙ Negate ∙ Signum ∙ Reciprocal ∙ Magnitude ∙ Exponential ∙ Natural Logarithm ∙ Floor ∙ Ceiling ∙ Factorial ∙ Not ∙ Pi Times ∙ Roll ∙ Type ∙ Imaginary ∙ Square Root ∙ Round
Dyadic Add ∙ Subtract ∙ Times ∙ Divide ∙ Residue ∙ Power ∙ Logarithm ∙ Minimum ∙ Maximum ∙ Binomial ∙ Comparison functions ∙ Boolean functions (And, Or, Nand, Nor) ∙ GCD ∙ LCM ∙ Circular ∙ Complex ∙ Root
Non-Scalar
Structural Shape ∙ Reshape ∙ Tally ∙ Depth ∙ Ravel ∙ Enlist ∙ Table ∙ Catenate ∙ Reverse ∙ Rotate ∙ Transpose ∙ Raze ∙ Mix ∙ Split ∙ Enclose ∙ Nest ∙ Cut (K) ∙ Pair ∙ Link ∙ Partitioned Enclose ∙ Partition
Selection First ∙ Pick ∙ Take ∙ Drop ∙ Unique ∙ Identity ∙ Stop ∙ Select ∙ Replicate ∙ Expand ∙ Set functions (Intersection ∙ Union ∙ Without) ∙ Bracket indexing ∙ Index ∙ Cartesian Product ∙ Sort
Selector Index generator ∙ Grade ∙ Index Of ∙ Interval Index ∙ Indices ∙ Deal ∙ Prefix and suffix vectors
Computational Match ∙ Not Match ∙ Membership ∙ Find ∙ Nub Sieve ∙ Encode ∙ Decode ∙ Matrix Inverse ∙ Matrix Divide ∙ Format ∙ Execute ∙ Materialise ∙ Range
Operators Monadic Each ∙ Commute ∙ Constant ∙ Replicate ∙ Expand ∙ Reduce ∙ Windowed Reduce ∙ Scan ∙ Outer Product ∙ Key ∙ I-Beam ∙ Spawn ∙ Function axis ∙ Identity (Null, Ident)
Dyadic Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator) ∙ Identity (Lev, Dex)
Quad names Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector
Retrieved from ‘https://aplwiki.com/index.php?title=Outer_Product&oldid=10402’