Free (rational) derivation
DOI:
https://doi.org/10.17398/2605-5686.36.1.25Keywords:
Hausdorff derivative, free associative algebra, free field, minimal linear representation, admissible linear system, free fractions, chain rule, Newton iterationAbstract
By representing elements in free fields (over a commutative field and a finite alphabet) using Cohn and Reutenauer’s linear representations, we provide an algorithmic construction for the (partial) non-commutative (or Hausdorff-) derivative and show how it can be applied to the non-commutative version of the Newton iteration to find roots of matrix-valued rational equations.
Downloads
References
G.M. Bergman, W. Dicks, On universal derivations, J. Algebra 36 (2) (1975), 193 – 211.
J. Berstel, C. Reutenauer, “ Noncommutative Rational Series with Applications ”, Encyclopedia of Mathematics and its Applications, 137, Cambridge University Press, Cambridge, 2011.
J.F. Camino, J.W. Helton, R.E. Skelton, Solving matrix inequalities whose unknowns are matrices, SIAM J. Optim. 17 (1) (2006), 1 – 36.
J.F. Camino, J.W. Helton, R.E. Skelton, J. Ye, Matrix inequalities: a symbolic procedure to determine convexity automatically, Integral Equations Operator Theory 46 (4) (2003), 399 – 454.
P.M. Cohn, Around Sylvester’s law of nullity, Math. Sci. 14 (2) (1989), 73 – 83.
P.M. Cohn, “ Skew Fields. Theory of General Division Rings ”, Encyclopedia of Mathematics and its Applications, 57, Cambridge University Press, Cambridge, 1995.
P.M. Cohn, “ Further Algebra and Applications ”, Springer-Verlag London, Ltd., London, 2003.
P.M. Cohn, “ Free Ideal Rings and Localization in General Rings ”, New Mathematical Monographs, 3, Cambridge University Press, Cambridge, 2006.
P.M. Cohn, C. Reutenauer, A normal form in free fields, Canad. J. Math. 46 (3) (1994), 517–531.
P.M. Cohn, C. Reutenauer, On the construction of the free field, Internat. J. Algebra Comput. 9 (3-4) (1999), 307 – 323. Dedicated to the memory of Marcel-Paul Schützenberger.
J.W. Demmel, “ Applied Numerical Linear Algebra ”, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.
M.C. de Oliveira, J.W. Helton, Computer algebra tailored to matrix inequalities in control, Internat. J. Control 79 (11) (2006), 1382 – 1400.
E. Deadman, S.D. Relton, Taylor’s theorem for matrix functions with applications to condition number estimation, Linear Algebra Appl. 504 (2016), 354 – 371.
FriCAS team, FriCAS — An advanced computer algebra system, 2019. Release 1.3.5, available at http://fricas.sf.net, documentation http://fricas.github.io.
F.R. Gantmacher, “ Matrizenrechnung. Teil I. Allgemeine Theorie ”, Zweite, Berichtigte Auflage. Hochschulbücher für Mathematik, Band 36 VEB Deutscher Verlag der Wissenschaften, Berlin, 1965.
W. Hackbusch, “ Hierarchische Matrizen: Algorithmen und Analysis ”, Springer, Berlin, 2009.
P. Henrici, “ Elements of Numerical Analysis ”, John Wiley & Sons, Inc., New York-London-Sydney, 1964.
N.J. Higham, Newton’s method for the matrix square root, Math. Comp. 46 (174) (1986), 537 – 549.
N.J. Higham, “ Functions of Matrices. Theory and Computation ”, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008.
P. Kirrinnis, Fast algorithms for the Sylvester equation AX − XB | = C, Theoret. Comput. Sci. 259 (1-2) (2001), 623 – 638.
D.S. Kaliuzhnyi-Verbovetskyi, V. Vinnikov, “ Foundations of Free Noncommutative Function Theory ”, Mathematical Surveys and Monographs, 199, American Mathematical Society, Providence, RI, 2014.
LAPACK 3.5.0, 2018, http://www.netlib.org/lapack.
G. Popescu, Free holomorphic functions on the unit ball of B(H )n , J. Funct. Anal. 241 (1) (2006), 268 – 333.
C. Reutenauer, Cyclic derivation of noncommutative algebraic power series, J. Algebra 85 (1) (1983), 32 – 39.
C. Reutenauer, Applications of a noncommutative Jacobian matrix, J. Pure Appl. Algebra 77 (2) (1992), 169 – 181.
C. Reutenauer, Michel Fliess and non-commutative formal power series, Internat. J. Control 81 (3) (2008), 336 – 341.
G.-C. Rota, B. Sagan, P.R. Stein, A cyclic derivative in noncommutative algebra, J. Algebra 64 (1) (1980), 54 – 75.
S.M. Rump, Verification methods: rigorous results using floating-point arithmetic, Acta Numer. 19 (2010), 287 – 449.
K. Schrempf, Free fractions: An invitation to (applied) free fields, ArXiv e-prints, September 2018. Version 2, October 2020, http://arxiv.org/pdf/1809.05425.
K. Schrempf, Linearizing the word problem in (some) free fields, Internat. J. Algebra Comput. 28 (7) (2018), 1209 – 1230.
K. Schrempf, Horner Systems: How to efficiently evaluate non-commutative polynomials (by matrices), arXiv e-prints, October 2019.
K. Schrempf, A standard form in (some) free fields: How to construct minimal linear representations, Open Math. 18 (1) (2020), 1365 – 1386.
D. Schleicher, R. Stoll, Newton’s method in practice: Finding all roots of polynomials of degree one million efficiently, Theoret. Comput. Sci. 681 (2017), 146 – 166.
D. Voiculescu, A note on cyclic gradients, Indiana Univ. Math. J. 49 (3) (2000), 837 – 841.
