Outer Product: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
 
(21 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Built-in|Outer Product|<nowiki>∘.</nowiki>}}, or '''Table''' is a [[monadic operator]], which will produce a [[dyadic function]] when applied with a [[dyadic function]]. In APL, the outer product is a generalisation of the [https://en.wikipedia.org/wiki/Matrix_multiplication matrix product], which allows not only multiplication, but any [[dyadic function]] given. In short, outer product allows you to apply a given function on each element of the left array with each element of the right array. Basically, a shortcut for constructing nested [https://en.wikipedia.org/wiki/For_loop for loop]s.
{{Built-in|Outer Product|<nowiki>∘.</nowiki>}}, 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 [[wikipedia:for loop|for loop]]s, and as a structured [[wikipedia:Cartesian product|Cartesian product]] generalized to operations other than [[catenate|catenation]].


=== Syntax ===
=== Syntax ===
By right, a [[monadic operator]] should be a single [[glyph]], and the operand should be on the left. However, for [[backwards compatibility|historical reasons]], the outer product operator is not only a [[bi-glyph]] denoted as <source lang=apl inline>∘.</source>, the operand also appears on the right instead.
Outer Product differs from all other [[monadic operator]]s, which are written as a single [[glyph]], with the operand on the left. For [[backwards compatibility|historical reasons]], the outer product operator is a [[bi-glyph]] denoted as <syntaxhighlight lang=apl inline>∘.</syntaxhighlight>, and its operand appears on the right. This special notation is derived from the <syntaxhighlight lang=apl inline>f.g</syntaxhighlight> notation of [[inner product]]:<ref>[[Adin Falkoff|Falkoff, A.D.]] and [[Ken Iverson|K.E. Iverson]]. [https://www.jsoftware.com/papers/APL360TerminalSystem1.htm#ip The APL\360 Terminal System: Inner and Outer Products]. Research Report RC-1922. IBM [[Watson Research Center]]. 1967-10-16.</ref>
<blockquote>
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 <code>a∘.×b</code> .
</blockquote>
This syntactical inconsistency is resolved in [[J]] and [[BQN]], where the outer product operator, called Table, and denoted <syntaxhighlight lang=j inline>/</syntaxhighlight> and <code>⌜</code> respectively, has the usual operator syntax.


Notably, this syntactical inconsistency is resolved in [[J]] and [[BQN]], where the outer product operator, called Table, and denoted <source lang=j inline>/</source> and <code>⌜</code> respectively, abide by the usual operator syntax.
=== Model ===
Outer Product can be modeled as <syntaxhighlight lang=apl inline>f¨⍤0 99</syntaxhighlight>.


=== Examples ===
=== Examples ===
<source lang=apl>
<syntaxhighlight lang=apl>
       x ← 1 2 3
       x ← 1 2 3
       y ← 4 5 6
       y ← 4 5 6
Line 18: Line 23:
│3 4│3 5│3 6│
│3 4│3 5│3 6│
└───┴───┴───┘
└───┴───┴───┘
      x ∘.× y ⍝ matrix multiplication
4  5  6
8 10 12
12 15 18


       ⍝ works for multi-dimensional arrays as well
       ⍝ works for multi-dimensional arrays as well
Line 49: Line 50:
└───┴───┴───┘
└───┴───┴───┘
        
        
</source>
</syntaxhighlight>


=== Applications ===
=== Applications ===
Outer product is useful for solving problems that intuitively requires a [https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time polynomial time] algorithm.  
Outer product is useful for solving problems that intuitively require a [[wikipedia:Time_complexity#Polynomial_time|polynomial time]] algorithm. This may also indicate that such an algorithm is not the fastest solution.
However, this also indicates that such an algorithm might not be 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.
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.
<source lang=apl>
<syntaxhighlight lang=apl>
       x ← 1 2 3 2
       x ← 1 2 3 2
       ⎕ ← matrix ← x∘.=x ⍝ compare elements with each other using equal
       ⎕ ← matrix ← x∘.=x ⍝ compare elements with each other using equal
Line 74: Line 74:
       (⊢∪⍤/⍨2≤(+/∘.=⍨)) x ⍝ point-free/tacit version
       (⊢∪⍤/⍨2≤(+/∘.=⍨)) x ⍝ point-free/tacit version
2
2
</source>
</syntaxhighlight>
Using similar techniques, we can define a function that generates prime numbers by using an outer product of [[Residue]].
Using similar techniques, we can define a function that generates prime numbers by using an outer product of [[Residue]].
<source lang=apl>
<syntaxhighlight lang=apl>
     primes ← {x←1↓⍳⍵ ⋄ (2>+⌿0=x∘.|x)/x}
     primes ← {x←1↓⍳⍵ ⋄ (2>+⌿0=x∘.|x)/x}
     primes 10
     primes 10
Line 82: Line 82:
       primes 20
       primes 20
2 3 5 7 11 13 17 19
2 3 5 7 11 13 17 19
</source>
</syntaxhighlight>
Again, using outer product might not yield the fastest solution. There are faster solutions such as [https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Sieve of Eratosthenes].
Here there are faster solutions such as the [[wikipedia:Sieve of Eratosthenes|Sieve of Eratosthenes]].
 
=== Differences between dialects ===
[[J]]'s Table differs from APL's Outer Product by enabling Cartesian pairing between [[cell]]s of [[rank]]s 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 <syntaxhighlight lang=j inline>u"(lu, _)</syntaxhighlight>, where <syntaxhighlight lang=j inline>lu</syntaxhighlight> is the left rank of operand <syntaxhighlight lang=j inline>u</syntaxhighlight> (<syntaxhighlight lang=j inline>"</syntaxhighlight> and <syntaxhighlight lang=j inline>_</syntaxhighlight> denote [[rank_(operator)|Rank]] and infinity, respectively, in J).
 
<syntaxhighlight lang=j>
  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│
└───────┴───────────┘
</syntaxhighlight>
{{Works in|[[J]]}}
 
In APL this behavior can be accomplished by enclosing the relevant cells of each argument before applying the outer product operation (or by successive applications of Rank, e.g. <syntaxhighlight lang=apl inline>f⍤99 1⍤2 99</syntaxhighlight>). Conversely, the behavior of APL's Outer Product on nested inputs can be accomplished in terms of J's Table by adding the Each modifier, as in <syntaxhighlight lang=j inline>u&.>/</syntaxhighlight>.
 
The results of the individual applications of u are collectively [[frame]]d 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.  
 
Table does not allow for creating a Cartesian pairing involving cells of the left argument specified with negative rank (except trivially, in cases in which Table's application has no effect, e.g. <syntaxhighlight lang=j inline>u"_ _1"_2 _/</syntaxhighlight>). This is because negative assigned rank in J is encoded as infinite rank; in J's terminology, negative rank is "internal rank" only.
<syntaxhighlight lang=j>
  }.+"_1 _2 b.0  NB. dyadic ranks of derived verb +"_1 _2 as seen by Table
_ _
</syntaxhighlight>
 
== External links ==
== External links ==
* [https://mlochbaum.github.io/OuterProduct/ Outer Product as an Introduction to APL and a Pretty Cool Thing in General]: website for LambdaConf talk by [[Marshall Lochbaum]]


=== Documentation ===
=== Documentation ===
Line 91: Line 154:
* [https://microapl.com/apl_help/ch_020_020_890.htm APLX]
* [https://microapl.com/apl_help/ch_020_020_890.htm APLX]
* J [https://www.jsoftware.com/help/dictionary/d420.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/slash#dyadic NuVoc]
* J [https://www.jsoftware.com/help/dictionary/d420.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/slash#dyadic NuVoc]
* [https://mlochbaum.github.io/BQN/doc/map.html#table BQN]


== References ==
<references/>
{{APL built-ins}}[[Category:Primitive operators]]
{{APL built-ins}}[[Category:Primitive operators]]

Latest revision as of 00:47, 19 March 2024

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 structured Cartesian product generalized 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 (" and _ denote Rank and infinity, respectively, in J).

   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 this behavior can be accomplished by enclosing the relevant cells of each argument before applying the outer product operation (or by successive applications of Rank, e.g. f⍤99 1⍤2 99). Conversely, the behavior of APL's Outer Product on nested inputs can be accomplished in terms of J's Table by adding the Each modifier, as in u&.>/.

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.

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

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

External links

Documentation

References

APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic ConjugateNegateSignumReciprocalMagnitudeExponentialNatural LogarithmFloorCeilingFactorialNotPi TimesRollTypeImaginarySquare Root
Dyadic AddSubtractTimesDivideResiduePowerLogarithmMinimumMaximumBinomialComparison functionsBoolean functions (And, Or, Nand, Nor) ∙ GCDLCMCircularComplexRoot
Non-Scalar
Structural ShapeReshapeTallyDepthRavelEnlistTableCatenateReverseRotateTransposeRazeMixSplitEncloseNestCut (K)PairLinkPartitioned EnclosePartition
Selection FirstPickTakeDropUniqueIdentityStopSelectReplicateExpandSet functions (IntersectionUnionWithout) ∙ Bracket indexingIndexCartesian ProductSort
Selector Index generatorGradeIndex OfInterval IndexIndicesDealPrefix and suffix vectors
Computational MatchNot MatchMembershipFindNub SieveEncodeDecodeMatrix InverseMatrix DivideFormatExecuteMaterialiseRange
Operators Monadic EachCommuteConstantReplicateExpandReduceWindowed ReduceScanOuter ProductKeyI-BeamSpawnFunction axis
Dyadic BindCompositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner ProductDeterminantPowerAtUnderRankDepthVariantStencilCutDirect definition (operator)
Quad names Index originComparison toleranceMigration levelAtomic vector