Determinant: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
(Created page with "{{Built-in|Determinant|<nowiki>.</nowiki>}} is a primitive dyadic operator that takes two dyadic functions for operands and produces a monadic function. Much like Inner Product for matrix products, it generalizes the matrix wikipedia:determinant, so that <source lang=apl inline>-.×</source> computes the determinant and <source lang=apl inline>+.×</source> the wikipedia:permanent (mathematics). Determinant has been implemented in SHAR...")
 
(Mention Rationalized APL, Dictionary APL)
 
Line 3: Line 3:
Unlike the inner product operator, which performs <math>O(n^3)</math> arithmetic operations on square matrices of side length <math>n</math> given arithmetic operands, definitions of the determinant use a super-polynomial number of evaluations, for example <math>O(n\cdot n!)</math> in SHARP APL's definition. [[wikipedia:Computing the permanent|Computing the permanent]] in particular is not believed to be possible in polynomial time, which would rule out a polynomial-time definition for any generalization of it. The specific determinant function <source lang=apl inline>-.×</source> can be computed much faster (for example by LU decomposition in <math>O(n^3)</math>), and is always handled specially for performance. Other combinations of operands may also have optimized implementations.
Unlike the inner product operator, which performs <math>O(n^3)</math> arithmetic operations on square matrices of side length <math>n</math> given arithmetic operands, definitions of the determinant use a super-polynomial number of evaluations, for example <math>O(n\cdot n!)</math> in SHARP APL's definition. [[wikipedia:Computing the permanent|Computing the permanent]] in particular is not believed to be possible in polynomial time, which would rule out a polynomial-time definition for any generalization of it. The specific determinant function <source lang=apl inline>-.×</source> can be computed much faster (for example by LU decomposition in <math>O(n^3)</math>), and is always handled specially for performance. Other combinations of operands may also have optimized implementations.


The determinant operator was described by [[Ken Iverson]] in "Determinant-Like Functions Produced by the Dot Operator"<ref>[[Ken Iverson]]. SATN-42: [https://www.jsoftware.com/papers/satn42.htm Determinant-Like Functions Produced by the Dot Operator]. 1982-04-01.</ref> and also implemented in [[SHARP APL]]<ref>IPSA Newsletter July/August 1982 ([https://www.snakeisland.com/IPSANewsletter_1982_07_08.pdf pdf])</ref> in 1982.
The determinant operator was described by [[Ken Iverson]] in "Determinant-Like Functions Produced by the Dot Operator"<ref>[[Ken Iverson]]. SATN-42: [https://www.jsoftware.com/papers/satn42.htm Determinant-Like Functions Produced by the Dot Operator]. 1982-04-01.</ref> and also implemented in [[SHARP APL]]<ref>IPSA Newsletter July/August 1982 ([https://www.snakeisland.com/IPSANewsletter_1982_07_08.pdf pdf])</ref> in 1982. It also appears in Iverson's later publications [[Rationalized APL]] and [[A Dictionary of APL]].


== Documentation ==
== Documentation ==

Latest revision as of 01:00, 5 March 2024

.

Determinant (.) is a primitive dyadic operator that takes two dyadic functions for operands and produces a monadic function. Much like Inner Product for matrix products, it generalizes the matrix determinant, so that -.× computes the determinant and +.× the permanent. Determinant has been implemented in SHARP APL, NARS2000, and J; however, the J definition differs by factoring out a reduction from the definition, so that -/ .* is the matrix determinant.

Unlike the inner product operator, which performs arithmetic operations on square matrices of side length given arithmetic operands, definitions of the determinant use a super-polynomial number of evaluations, for example in SHARP APL's definition. Computing the permanent in particular is not believed to be possible in polynomial time, which would rule out a polynomial-time definition for any generalization of it. The specific determinant function -.× can be computed much faster (for example by LU decomposition in ), and is always handled specially for performance. Other combinations of operands may also have optimized implementations.

The determinant operator was described by Ken Iverson in "Determinant-Like Functions Produced by the Dot Operator"[1] and also implemented in SHARP APL[2] in 1982. It also appears in Iverson's later publications Rationalized APL and A Dictionary of APL.

Documentation

References

  1. ↑ Ken Iverson. SATN-42: Determinant-Like Functions Produced by the Dot Operator. 1982-04-01.
  2. ↑ IPSA Newsletter July/August 1982 (pdf)
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=Determinant&oldid=11170’