2,954
edits
Inner Product: Difference between revisions
Jump to navigation
Jump to search
m
→Differences between dialects: ISO/IEC 13751:2001 link
m (Text replacement - "<source" to "<syntaxhighlight") |
m (→Differences between dialects: ISO/IEC 13751:2001 link) |
||
| (12 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{Built-in|Inner Product|<nowiki>.</nowiki>}} is a [[dyadic operator]] that produces a [[dyadic function]] when applied with two dyadic functions. It's a generalisation of the [[wikipedia:Matrix multiplication|matrix product]], allowing not just addition-multiplication, but any [[dyadic function]]s given as [[operand]]s. | {{Built-in|Inner Product|<nowiki>.</nowiki>}} is a [[dyadic operator]] that produces a [[dyadic function]] when applied with two dyadic functions. It's a generalisation of the [[wikipedia:Matrix multiplication|matrix product]], allowing not just addition-multiplication, but any [[dyadic function]]s given as [[operand]]s. | ||
== Description == | |||
For each rank-1 cell in the arguments, inner product applies <syntaxhighlight lang=apl inline>⍵⍵</syntaxhighlight> between the two and then applies <syntaxhighlight lang=apl inline>⍺⍺⌿</syntaxhighlight> to the results of those invocations. If the arguments themselves are simply vectors, there is only one rank-1 cell in each argument, so this results in the following application pattern: | |||
<syntaxhighlight lang=apl> | |||
1 2 3 4 F.G 5 6 7 8 | |||
(1 G 5) F (2 G 6) F (3 G 7) F (4 G 8) | |||
</syntaxhighlight> | |||
The second line is an illustration of how the first will be evaluated. Note that this is precisely the [[wikipedia:Dot product|vector dot product]] when used as <syntaxhighlight lang=apl inline>+.×</syntaxhighlight>. (This simple invocation with vector arguments will be referred to as the "vector inner product" below, but it is just a simple case of the general inner product.) | |||
For matrix arguments, there may be more than one rank-1 cell. Considering the case of rank-2 matrices as arguments, if there are N rows in <syntaxhighlight lang=apl inline>⍺</syntaxhighlight> and M columns in <syntaxhighlight lang=apl inline>⍵</syntaxhighlight>, the result will be a matrix with N rows and M columns. Each row of the resulting matrix will correspond to the elements of that same row in <syntaxhighlight lang=apl inline>⍺</syntaxhighlight> being paired up with elements in a column of <syntaxhighlight lang=apl inline>⍵</syntaxhighlight>. Likewise, each column of the resulting matrix will correspond to the elements of that same column of <syntaxhighlight lang=apl inline>⍵</syntaxhighlight> being paired up with elements in a row of <syntaxhighlight lang=apl inline>⍺</syntaxhighlight>. '''Important: This means that the inner product will be applied for each ''row'' of <syntaxhighlight lang=apl inline>⍺</syntaxhighlight> but each ''column'' of <syntaxhighlight lang=apl inline>⍵</syntaxhighlight>!''' | |||
In practice, this means that the upper left element of the resulting matrix will correspond to performing the vector inner product on the first row of <syntaxhighlight lang=apl inline>⍺</syntaxhighlight> and the first column of <syntaxhighlight lang=apl inline>⍵</syntaxhighlight>, the upper right element will correspond to performing the vector inner product on the first row of <syntaxhighlight lang=apl inline>⍺</syntaxhighlight> and the last column of <syntaxhighlight lang=apl inline>⍵</syntaxhighlight>, the lower right element will correspond to the vector inner product on the last row of <syntaxhighlight lang=apl inline>⍺</syntaxhighlight> and the last column of <syntaxhighlight lang=apl inline>⍵</syntaxhighlight>, and so on and so on. Pictorially, then, for a 2x2 result we can represent the resulting matrix as: | |||
<syntaxhighlight lang=apl> | |||
┌──────────────────────────────┬──────────────────────────────┐ | |||
│(Row 1 of ⍺) F.G (Col. 1 of ⍵)│(Row 1 of ⍺) F.G (Col. 2 of ⍵)│ | |||
├──────────────────────────────┼──────────────────────────────┤ | |||
│(Row 2 of ⍺) F.G (Col. 1 of ⍵)│(Row 2 of ⍺) F.G (Col. 2 of ⍵)│ | |||
└──────────────────────────────┴──────────────────────────────┘ | |||
</syntaxhighlight> | |||
Note how the columns of <syntaxhighlight lang=apl inline>⍵</syntaxhighlight> align with the columns of the matrix, and the rows of <syntaxhighlight lang=apl inline>⍺</syntaxhighlight> align with the rows of the matrix. | |||
The concept readily generalizes to matrices of higher rank. | |||
== Examples == | == Examples == | ||
| Line 23: | Line 48: | ||
x+.×y ⍝ matrix multiplication | x+.×y ⍝ matrix multiplication | ||
32 | 32 | ||
</ | </syntaxhighlight> | ||
The [[shape]]s of the arguments must be compatible with each other: The last [[axis]] of the left argument must have the same length as the first axis of the right argument, or formally, for <syntaxhighlight lang=apl inline>X f.g Y</ | The [[shape]]s of the arguments must be compatible with each other: The last [[axis]] of the left argument must have the same length as the first axis of the right argument, or formally, for <syntaxhighlight lang=apl inline>X f.g Y</syntaxhighlight> it must be that <syntaxhighlight lang=apl inline>(¯1↑⍴X)≡(1↑⍴Y)</syntaxhighlight>. Although this rule differs from [[conformability]], the arguments may also be subject to [[scalar extension|scalar]] or [[singleton extension]]. The shape of the result is <syntaxhighlight lang=apl inline>(¯1↓⍴X),(1↓⍴Y)</syntaxhighlight>. | ||
For example, when applying inner product on two [[matrix|matrices]], the number of columns in the left array must match with number of rows in the right array, otherwise we will get an error. | For example, when applying inner product on two [[matrix|matrices]], the number of columns in the left array must match with number of rows in the right array, otherwise we will get an error. | ||
| Line 45: | Line 70: | ||
22 28 | 22 28 | ||
49 64 | 49 64 | ||
</ | </syntaxhighlight> | ||
== History == | == History == | ||
Inner product appeared in early [[Iverson Notation]] as <math>^f_g</math> and applied even to non-[[scalar function]]s, like [[Compress]], Iverson bringing:<ref>[[Ken Iverson]]. [[A Programming Language]]. §1.11 ''The language''.</ref> | Inner product appeared in early [[Iverson Notation]] as <math>^f_g</math> and applied even to non-[[scalar function]]s, like [[Compress]], Iverson bringing:<ref>[[Ken Iverson]]. [[A Programming Language]]. §1.11 ''The language''.</ref> | ||
| Line 68: | Line 93: | ||
20&4\\ | 20&4\\ | ||
\end{pmatrix}, | \end{pmatrix}, | ||
\quad\boldsymbol{A}\;^\ | \quad\boldsymbol{A}\;^\land_=\,\boldsymbol{B}=\begin{pmatrix} | ||
0&1\\ | 0&1\\ | ||
0&0\\ | 0&0\\ | ||
1&0\\ | 1&0\\ | ||
\end{pmatrix}\text{,}\\ | \end{pmatrix}\text{,}\\ | ||
\boldsymbol{A}\;^\ | \boldsymbol{A}\;^\lor_\neq\;\boldsymbol{B}&=\begin{pmatrix} | ||
1&0\\ | 1&0\\ | ||
1&1\\ | 1&1\\ | ||
| Line 85: | Line 110: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
When the inner product notation was linearised (made to fit on a single line of code) the [[glyph]] <syntaxhighlight lang=apl inline>.</ | When the inner product notation was linearised (made to fit on a single line of code) the [[glyph]] <syntaxhighlight lang=apl inline>.</syntaxhighlight> was chosed to denote what was previously indicated by positioning the two [[operand]]s vertically aligned. Thus, the above correspond to the following modern APL: | ||
<syntaxhighlight lang=apl> | <syntaxhighlight lang=apl> | ||
⍝ For example, if | ⍝ For example, if | ||
| Line 107: | Line 132: | ||
6 4 | 6 4 | ||
6 1 | 6 1 | ||
</ | </syntaxhighlight> | ||
Note that some dialects implement [[Compress]] (<syntaxhighlight lang=apl inline>/</ | Note that some dialects implement [[Compress]] (<syntaxhighlight lang=apl inline>/</syntaxhighlight>) as a [[monadic operator]] rather than as a function, which means it cannot be an operand in the inner product. Instead, a cover function is necessary: | ||
<syntaxhighlight lang=apl> | <syntaxhighlight lang=apl> | ||
∇z←a Compress b | ∇z←a Compress b | ||
z←a/b | z←a/b | ||
∇ | ∇ | ||
</ | </syntaxhighlight> | ||
== Differences between dialects == | == Differences between dialects == | ||
Implementations differ on the exact behaviour of inner product when the right operand is not a [[scalar function]]. | Implementations differ on the exact behaviour of inner product when the right operand is not a [[scalar function]]. Page 121 of the [[ISO/IEC 13751:2001]] standard specifies that <syntaxhighlight lang=apl inline>X f.g Y</syntaxhighlight> is equivalent to <syntaxhighlight lang=apl>f/¨ (⊂[⍴⍴x]x)∘.g ⊂[1]y</syntaxhighlight> (assuming [[index origin]] 1). This is indeed what [[APL2]], [[APLX]], [[APL+Win]], and [[ngn/apl]] follow, while [[Dyalog APL]], [[NARS2000]] and [[GNU APL]] differ as described by [[Roger Hui]]:<ref>[[Roger Hui]]. ''inner product''. Internal Dyalog email. 24 July 2020.</ref> | ||
<blockquote> | <blockquote> | ||
The following dop models inner product in Dyalog APL, with caveats. If you find a case where <syntaxhighlight lang=apl inline>f.g</ | The following dop models inner product in Dyalog APL, with caveats. If you find a case where <syntaxhighlight lang=apl inline>f.g</syntaxhighlight> differs from <syntaxhighlight lang=apl inline>f IP g</syntaxhighlight>, not covered by the caveats, I'd be interested. | ||
<syntaxhighlight lang=apl> | <syntaxhighlight lang=apl> | ||
IP←{ | IP←{ | ||
| Line 126: | Line 151: | ||
assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕SIGNAL 8 ⋄ shy←0} | assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕SIGNAL 8 ⋄ shy←0} | ||
</ | </syntaxhighlight> | ||
(Explanation: What's with the <syntaxhighlight lang=apl inline>⊃⍤0</ | (Explanation: What's with the <syntaxhighlight lang=apl inline>⊃⍤0</syntaxhighlight> in <syntaxhighlight lang=apl inline>IP</syntaxhighlight>? It's because <syntaxhighlight lang=apl inline>∘.f</syntaxhighlight> has an implicit each, applying <syntaxhighlight lang=apl inline>⊂</syntaxhighlight> to each item of its result. But the <syntaxhighlight lang=apl inline>⍺⍺/</syntaxhighlight> in <syntaxhighlight lang=apl inline>(⍺⍺/⍵⍵¨)</syntaxhighlight> also has an implicit each. So the <syntaxhighlight lang=apl inline>⊃⍤0</syntaxhighlight> gets rid of one of those encloses.) | ||
Caveats: | Caveats: | ||
* You can not use the hybrid <syntaxhighlight lang=apl inline>/</ | * You can not use the hybrid <syntaxhighlight lang=apl inline>/</syntaxhighlight> directly as an operand as it runs afoul of the parser in weird and wonderful ways. Instead, you have to use <syntaxhighlight lang=apl inline>{⍺/⍵}</syntaxhighlight>. The same goes for <syntaxhighlight lang=apl inline>\</syntaxhighlight> and <syntaxhighlight lang=apl inline>{⍺\⍵}</syntaxhighlight> I guess. | ||
* It differs from ISO/IEC 13751:2001(E) in using <syntaxhighlight lang=apl inline>⍵⍵¨</ | * It differs from ISO/IEC 13751:2001(E) in using <syntaxhighlight lang=apl inline>⍵⍵¨</syntaxhighlight> instead of just <syntaxhighlight lang=apl inline>⍵⍵</syntaxhighlight> in the central key expression (i.e. <syntaxhighlight lang=apl inline>(⍺⍺/⍵⍵¨)</syntaxhighlight> instead of <syntaxhighlight lang=apl inline>(⍺⍺/⍵⍵)</syntaxhighlight>). So does the primitive <syntaxhighlight lang=apl inline>f.g</syntaxhighlight>. | ||
* It differs from ISO/IEC 13751:2001(E) in doing full-blown single extension instead of just scalar and 1-element vector extension (as in APL2). So does the primitive <syntaxhighlight lang=apl inline>f.g</ | * It differs from ISO/IEC 13751:2001(E) in doing full-blown single extension instead of just scalar and 1-element vector extension (as in APL2). So does the primitive <syntaxhighlight lang=apl inline>f.g</syntaxhighlight>. e.g.<syntaxhighlight lang=apl> | ||
(3 4⍴5)+.×1 1 1 1⍴6 ⍝ works in Dyalog, not in ISO or APL2</ | (3 4⍴5)+.×1 1 1 1⍴6 ⍝ works in Dyalog, not in ISO or APL2</syntaxhighlight> | ||
* It differs from NARS2000 or APL\360 in not permitting unit axis extension. So does the primitive <syntaxhighlight lang=apl inline>f.g</ | * It differs from NARS2000 or APL\360 in not permitting unit axis extension. So does the primitive <syntaxhighlight lang=apl inline>f.g</syntaxhighlight>. e.g.<syntaxhighlight lang=apl> | ||
(3 4⍴5)+.×1 5⍴6 ⍝ works in NARS2000 or APL\360, not in Dyalog APL</ | (3 4⍴5)+.×1 5⍴6 ⍝ works in NARS2000 or APL\360, not in Dyalog APL</syntaxhighlight> | ||
</blockquote> | </blockquote> | ||
The <syntaxhighlight lang=apl>⊃⍤0⊢(↓⍺)∘.(⍺⍺/⍵⍵¨)↓(¯1⌽⍳⍴⍴⍵)⍉⍵</syntaxhighlight> line of IP above can be rewritten as <syntaxhighlight lang=apl>⍺(⍺⍺⌿⍵⍵¨⍤¯1)⍤1 99⊢⍵</syntaxhighlight> which uses the more efficient [[item]]-at-a-time algorithm (rather than row-by-column). The ISO/IEC 13751:2001(E) inner product, conversely, can only be calculated row-by-column, as computing the results one item (of the right argument) at a time relies on each application of the right operand being done between two scalars and producing a scalar result—that is, on the [[Each]] operator being applied to the right operand. | |||
Some implementations extend the inner product by implementing Iverson's monadic variant<ref>[[Ken Iverson|K.E. Iverson]]. [https://www.jsoftware.com/papers/satn42.htm Determinant-Like Functions Produced by the Dot Operator.] SHARP APL Technical Note 42. 1982-04-01.</ref>, which takes a single argument and performs the operation of computing the alternant, as modelled by [https://dfns.dyalog.com/n_alt.htm dfns.alt]. | |||
== External links == | == External links == | ||
| Line 148: | Line 176: | ||
* [https://microapl.com/apl_help/ch_020_020_880.htm APLX] | * [https://microapl.com/apl_help/ch_020_020_880.htm APLX] | ||
* J [https://www.jsoftware.com/help/dictionary/d300.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/dot#dyadic NuVoc] | * J [https://www.jsoftware.com/help/dictionary/d300.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/dot#dyadic NuVoc] | ||
=== Publications === | |||
* [https://www.jsoftware.com/papers/innerproduct/ip1.htm Inner Product: An Old/New Problem] by [[Roger Hui]] | |||
=== Discussion of differences between dialects === | === Discussion of differences between dialects === | ||