×

Free (rational) derivation. (English) Zbl 1490.16068

Summary: 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.

MSC:

16S85 Associative rings of fractions and localizations
16K40 Infinite-dimensional and general division rings
16S10 Associative rings determined by universal properties (free algebras, coproducts, adjunction of inverses, etc.)

Software:

mftoolbox
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] G.M. Bergman, W. Dicks,On universal derivations,J. Algebra36(2) (1975), 193 - 211. · Zbl 0271.16017
[2] J. Berstel, C. Reutenauer,“ Noncommutative Rational Series with Applications ”, Encyclopedia of Mathematics and its Applications, 137, Cambridge University Press, Cambridge, 2011. · Zbl 1250.68007
[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. · Zbl 1112.90058
[4] J.F. Camino, J.W. Helton, R.E. Skelton, J. Ye,Matrix inequalities: a symbolic procedure to determine convexity automatically,Integral Equations Operator Theory46(4) (2003), 399 - 454. · Zbl 1046.68139
[5] P.M. Cohn,Around Sylvester’s law of nullity,Math. Sci.14(2) (1989), 73 - 83. · Zbl 0686.15005
[6] P.M. Cohn,“ Skew Fields. Theory of General Division Rings ”, Encyclopedia of Mathematics and its Applications, 57, Cambridge University Press, Cambridge, 1995. · Zbl 0840.16001
[7] P.M. Cohn,“ Further Algebra and Applications ”, Springer-Verlag London, Ltd., London, 2003. · Zbl 1006.00001
[8] P.M. Cohn,“ Free Ideal Rings and Localization in General Rings ”, New Mathematical Monographs, 3, Cambridge University Press, Cambridge, 2006. · Zbl 1114.16001
[9] P.M. Cohn, C. Reutenauer,A normal form in free fields,Canad. J. Math. 46(3) (1994), 517-531. · Zbl 0836.16012
[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¨utzenberger. · Zbl 1040.16015
[11] J.W. Demmel,“ Applied Numerical Linear Algebra ”, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. · Zbl 0879.65017
[12] M.C. de Oliveira, J.W. Helton,Computer algebra tailored to matrix inequalities in control,Internat. J. Control79(11) (2006), 1382 - 1400. · Zbl 1133.93333
[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. · Zbl 1338.15016
[14] FriCAS team,FriCAS — An advanced computer algebra system, 2019. Release 1.3.5, available athttp://fricas.sf.net, documentationhttp: //fricas.github.io.
[15] F.R. Gantmacher,“ Matrizenrechnung. Teil I. Allgemeine Theorie ”, Zweite, Berichtigte Auflage. Hochschulb¨ucher f¨ur Mathematik, Band 36 VEB Deutscher Verlag der Wissenschaften, Berlin, 1965.
[16] W. Hackbusch,“ Hierarchische Matrizen:Algorithmen und Analysis ”, Springer, Berlin, 2009. · Zbl 1180.65004
[17] P. Henrici,“ Elements of Numerical Analysis ”, John Wiley & Sons, Inc., New York-London-Sydney, 1964. · Zbl 0149.10901
[18] N.J. Higham,Newton’s method for the matrix square root,Math. Comp. 46(174) (1986), 537 - 549. · Zbl 0614.65045
[19] N.J. Higham,“ Functions of Matrices. Theory and Computation ”, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. · Zbl 1167.15001
[20] P. Kirrinnis,Fast algorithms for the Sylvester equationAX−XB|=C, Theoret. Comput. Sci.259(1-2) (2001), 623 - 638. · Zbl 0972.68183
[21] D.S. Kaliuzhnyi-Verbovetskyi, V. Vinnikov,“ Foundations of Free Noncommutative Function Theory ”, Mathematical Surveys and Monographs, 199, American Mathematical Society, Providence, RI, 2014. · Zbl 1312.46003
[22] LAPACK 3.5.0, 2018,http://www.netlib.org/lapack.
[23] G. Popescu,Free holomorphic functions on the unit ball ofB(H)n,J. Funct. Anal.241(1) (2006), 268 - 333. · Zbl 1112.47004
[24] C. Reutenauer,Cyclic derivation of noncommutative algebraic power series, J. Algebra85(1) (1983), 32 - 39. · Zbl 0523.16025
[25] C. Reutenauer,Applications of a noncommutative Jacobian matrix,J. Pure Appl. Algebra77(2) (1992), 169 - 181. · Zbl 0746.16016
[26] C. Reutenauer,Michel Fliess and non-commutative formal power series, Internat. J. Control81(3) (2008), 336 - 341. · Zbl 1152.68467
[27] G.-C. Rota, B. Sagan, P.R. Stein,A cyclic derivative in noncommutative algebra,J. Algebra64(1) (1980), 54 - 75. · Zbl 0428.16036
[28] S.M. Rump,Verification methods: rigorous results using floating-point arithmetic,Acta Numer.19(2010), 287 - 449. · Zbl 1323.65046
[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. · Zbl 1400.16010
[30] K. Schrempf,Linearizing the word problem in (some) free fields,Internat. J. Algebra Comput.28(7) (2018), 1209 - 1230. · Zbl 1400.16010
[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. · Zbl 1485.16016
[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. · Zbl 1375.65068
[34] D. Voiculescu,A note on cyclic gradients,Indiana Univ. Math. J.49(3) (2000), 837 - 841 · Zbl 1007.16026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.