Free (rational) derivation

Main Article Content

K. Schrempf

Abstract

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

Download data is not yet available.

Metrics

Metrics Loading ...

Article Details

How to Cite
Schrempf, K. (2021). Free (rational) derivation. Extracta Mathematicae, 36(1), 25-50. https://doi.org/10.17398/2605-5686.36.1.25
Section
Algebra

References

[1] G.M. Bergman, W. Dicks, On universal derivations, J. Algebra 36 (2) (1975), 193 – 211.
[2] J. Berstel, C. Reutenauer, “ Noncommutative Rational Series with Applications ”, Encyclopedia of Mathematics and its Applications, 137, Cambridge University Press, Cambridge, 2011.
[3] J.F. Camino, J.W. Helton, R.E. Skelton, Solving matrix inequalities whose unknowns are matrices, SIAM J. Optim. 17 (1) (2006), 1 – 36.
[4] 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.
[5] P.M. Cohn, Around Sylvester’s law of nullity, Math. Sci. 14 (2) (1989), 73 – 83.
[6] P.M. Cohn, “ Skew Fields. Theory of General Division Rings ”, Encyclopedia of Mathematics and its Applications, 57, Cambridge University Press, Cambridge, 1995.
[7] P.M. Cohn, “ Further Algebra and Applications ”, Springer-Verlag London, Ltd., London, 2003.
[8] P.M. Cohn, “ Free Ideal Rings and Localization in General Rings ”, New Mathematical Monographs, 3, Cambridge University Press, Cambridge, 2006.
[9] P.M. Cohn, C. Reutenauer, A normal form in free fields, Canad. J. Math. 46 (3) (1994), 517–531.
[10] 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.
[11] J.W. Demmel, “ Applied Numerical Linear Algebra ”, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.
[12] M.C. de Oliveira, J.W. Helton, Computer algebra tailored to matrix inequalities in control, Internat. J. Control 79 (11) (2006), 1382 – 1400.
[13] E. Deadman, S.D. Relton, Taylor’s theorem for matrix functions with applications to condition number estimation, Linear Algebra Appl. 504 (2016), 354 – 371.
[14] FriCAS team, FriCAS — An advanced computer algebra system, 2019. Release 1.3.5, available at http://fricas.sf.net, documentation http://fricas.github.io.
[15] 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.
[16] W. Hackbusch, “ Hierarchische Matrizen: Algorithmen und Analysis ”, Springer, Berlin, 2009.
[17] P. Henrici, “ Elements of Numerical Analysis ”, John Wiley & Sons, Inc., New York-London-Sydney, 1964.
[18] N.J. Higham, Newton’s method for the matrix square root, Math. Comp. 46 (174) (1986), 537 – 549.
[19] N.J. Higham, “ Functions of Matrices. Theory and Computation ”, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008.
[20] P. Kirrinnis, Fast algorithms for the Sylvester equation AX − XB | = C, Theoret. Comput. Sci. 259 (1-2) (2001), 623 – 638.
[21] D.S. Kaliuzhnyi-Verbovetskyi, V. Vinnikov, “ Foundations of Free Noncommutative Function Theory ”, Mathematical Surveys and Monographs, 199, American Mathematical Society, Providence, RI, 2014.
[22] LAPACK 3.5.0, 2018, http://www.netlib.org/lapack.
[23] G. Popescu, Free holomorphic functions on the unit ball of B(H )n , J. Funct. Anal. 241 (1) (2006), 268 – 333.
[24] C. Reutenauer, Cyclic derivation of noncommutative algebraic power series, J. Algebra 85 (1) (1983), 32 – 39.
[25] C. Reutenauer, Applications of a noncommutative Jacobian matrix, J. Pure Appl. Algebra 77 (2) (1992), 169 – 181.
[26] C. Reutenauer, Michel Fliess and non-commutative formal power series, Internat. J. Control 81 (3) (2008), 336 – 341.
[27] G.-C. Rota, B. Sagan, P.R. Stein, A cyclic derivative in noncommutative algebra, J. Algebra 64 (1) (1980), 54 – 75.
[28] S.M. Rump, Verification methods: rigorous results using floating-point arithmetic, Acta Numer. 19 (2010), 287 – 449.
[29] 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.
[30] K. Schrempf, Linearizing the word problem in (some) free fields, Internat. J. Algebra Comput. 28 (7) (2018), 1209 – 1230.
[31] K. Schrempf, Horner Systems: How to efficiently evaluate non-commutative polynomials (by matrices), arXiv e-prints, October 2019.
[32] K. Schrempf, A standard form in (some) free fields: How to construct minimal linear representations, Open Math. 18 (1) (2020), 1365 – 1386.
[33] 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.
[34] D. Voiculescu, A note on cyclic gradients, Indiana Univ. Math. J. 49 (3) (2000), 837 – 841.