2,954
edits
Determinant: Difference between revisions
Jump to navigation
Jump to search
Mention Rationalized APL, Dictionary APL
(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 == | ||