Talk:Polynomial evaluation

Edit request

• Specific text to be added at the end of Section Matrix Polynomials: Methods based on matrix polynomial multiplications and additions were proposed allowing to save nonscalar matrix multiplications with respect to the Paterson-Stockmeyer method .
• Reason for the change: New methods for evaluating matrix polynomials and matrix polynomial approximations more efficient than the Paterson-Stockmeyer were discovered. They are based on matrix polynomial multiplications and additions. Practical implementations of the methods allowing to save more non scalar matrix multiplications have been proposed . Methods of this kind have been used for accelerating the computation of the matrix exponential (http://dx.doi.org/10.1016/j.amc.2018.08.017, http://dx.doi.org/10.3390/math7121174, http://dx.doi.org/10.1016/j.matcom.2021.12.002), the matrix cosine and sine (http://dx.doi.org/10.1016/j.cam.2018.12.041, http://dx.doi.org/10.1016/j.apnum.2021.01.009), the matrix logarithm (https://doi.org/10.3390/math9172018) and the matrix hyperbolic tangent (http://dx.doi.org/10.3390/math9111219).

Some cites of the method are (see https://scholar.google.com/scholar?oi=bibs&hl=es&cites=15799961841987285747): , , , ,

• References supporting change:

Jorge Sastre (talk) 08:22, 10 August 2023 (UTC)

Jorge, it looks like your papers are about rational approximations, and the benefits of Padé Approximations over Taylor series, am I right?

Maybe you could add a new section about rational approximation or "mixed methods"? Thomasda (talk) 18:37, 23 November 2023 (UTC)

Dear Thomasda, it’s the contrary: with the recent matrix polynomial evaluation methods from https://doi.org/10.1016%2Fj.laa.2017.11.010 and further developments the polynomial approximations can be indeed more efficient than the Padé approximations (and also more than the mixed rational an polynomial approximations from http://dx.doi.org/10.1016/j.amc.2012.05.064). I could explain it further, but the edit should be as a COI, since I form part of the authors. If I propose the edit would you like to revise the text? Best Jorge Sastre (talk) 00:27, 24 November 2023 (UTC)

I see. What is the main result of "Efficient evaluation of matrix polynomials"? I can't find any theorems in there. Do you get better asymptotics that Stockmeyer in general?

Or is it an experimental paper for polynomials of size 1 to 16? Thomasda (talk) 13:55, 27 November 2023 (UTC)

There are both general cases and particular cases:

Proposition 1 from "Efficient evaluation of matrix polynomials" allows to save 1 matrix product with respect to the Paterson-Stockmeyer (PS) method for evaluating matrix polynomials of degree = 8 and degree >= 12, see Table 6, (restrictions apply)

Example 5.1 allows to evaluate a Taylor based approximation of degree 15 with 4 matrix products (the available degree with PS method is 9).

Proposition 2 generalizes Example 5.1 to higher polynomial degrees, however systems of multivariate polynomials which could have no solution may occur.

The result from Example 5.1 is generalized to any polynomial approximation of degree 15 in Proposition 1 from https://www.mdpi.com/2227-7390/9/14/1600 (restrictions apply).

Corollary 1 of this last reference allows to save 2 matrix products with respect to the PS method for matrix polynomials of degrees >= 30 (restrictions apply)

The last result (to appear in the reference below) allowed to evaluate a Taylor based approximation related to the matrix logarithm of degree 24 with 5 matrix products (only degree 12 is available with the PS method)

(Sastre, Jorge (2023). Advances on Evaluation of Matrix Polynomials Beyond the Paterson–Stockmeyer Method. in Proc. Mathematical Modelling in Engineering & Human Behaviour 2023, Springer, to appear: 1–7.)

In general we obtain the coefficients of our evaluation formulas by solving systems of multivariate polynomials. On the contrary, this reference https://dl.acm.org/doi/10.1145/3568991 proposes iterative methods allowing to obtain min-max polynomial approximations of matrix functions. We are working together with his author E. Jarlebring on a paper where a min-max approximation of degree up to 2^9=512 is obtained for certain matrix function. Jorge Sastre (talk) 23:33, 27 November 2023 (UTC)

The reference for evaluating a matrix polynomial approximation of degree 24+ with 5 non-scalar multiplications has been published, see pages 449-450 of https://imm.webs.upv.es/jornadas/proceedings/Modelling2023.pdf Jorge Sastre (talk) 13:37, 6 January 2024 (UTC)

References

Reply 10-AUG-2023

  Unable to review  

• Specific page numbers for the proposed references have not been provided. In most instances the page numbers provided were merely page ranges that the entire article appears upon:

1. Fasi source: page numbers 182-200 (18 pages)
2. Frommer source: pages 1674-1703 (29 pages)
3. Abdalla source: pages 1-28 (28 pages)
4. Jarlebring source: pages 1-35 (35 pages)
5. Kubelik source: pages 905-930 (25 pages)

• It is highly unlikely that the information proposed to be added to the article encompasses 135 pages in total. The COI editor is kindly asked to provide the specific page numbers from these sources where the proposed information is discussed.
• When ready to proceed with the requested information, kindly change the {{Edit COI}} template's answer parameter to read from |ans=y to |ans=n. Please note that prior text entered in the Edit request proposal should not be retro-actively altered. Instead, a new reply post supplying the needed information should be posted below this review. The original {{Edit COI}} template may then be altered.

Regards,  Spintendo  09:04, 10 August 2023 (UTC)

Thank you for your help, in the following corresponding texts from the articles and the corresponding pages have been included in the references:

"We note that the Paterson–Stockmeyer method is not the fastest known algorithm for evaluating polynomials of matrices: Paterson and Stockmeyer [17] discuss a technique that requires fewer matrix multiplications than the algorithm above, and an alternative approach for reducing the number of matrix multiplications to evaluate polynomials of matrices has recently been proposed by Sastre [18]" .

Fasi's article also cites as reference [20] the implementation of the matrix exponential using these methods from http://dx.doi.org/10.1016/j.amc.2018.08.017 .

"For the special case of polynomials approximating the exponential, approaches which further reduce the number of matrix multiplications were developed in [46, 47, 48]" on page 1677 . Section 3.7. "Further polynomial approximation techniques" from this article on pages 1688-1689 deals with the implementation boosting the matrix exponential computation as reference [47] cited above.

"Moreover, more recently many results concerting orthogonal matrix polynomials were introduced (see e.g. [66,68–70])" on page 14 (Reference [70]) .

"See Reference [34] for other approaches to evaluate rational approximants with few multiplications and left-divisions." p. 33 . This article also cites the article using this methods boosting the matrix exponential computation cited above as reference [38].

"See also modifications of the Paterson–Stockmeyer algorithm in [5, 50]." (reference [50]) p. 914 . Jorge Sastre (talk) 11:30, 11 August 2023 (UTC)

Thank you for your reply. In my review, I had asked you to provide the page numbers from these articles. You did that for 4 of the sources, but 6 were provided. You also mentioned page numbers where I was to look for references from other publications that are cited in the publications you provided (e.g., "See also modifications of the Paterson–Stockmeyer algorithm in [5, 50]." (reference [50]) p. 914"). Per WP:SWYGT, the original publication where the information resides is the one that should be used in the article. Your reply suggests that there are other references listed in the references you provided that contain the verifying information. The language addressing which references those are is also unclear (e.g., "For the special case of polynomials approximating the exponential, approaches which further reduce the number of matrix multiplications were developed in [46, 47, 48]" on page 1677" which doesn't state what 46, 47 and 48 came from, and "See Reference [34] for other approaches to evaluate rational approximants with few multiplications and left-divisions." p. 33" which doesn't state where reference 34 comes from) Additionally, secondary sources were not provided which discussed the journal publications you've mentioned. Please provide reliable secondary sources which discuss the information found in the publications you've presented. Regards,  Spintendo  08:34, 12 August 2023 (UTC)

Thank you for your help. The main reference proposing the matrix polynomial evaluation methods more efficient than the Paterson-Stockmeyer method dealt with this COI is reference [1] from the beggining of this talk page.

Fasi’s reference, Frommer’s reference, Abdalla’s reference, Jarlebring’s reference and Kubelik’s reference were some secondary sources from the main source [1] cited above. The source pages of the references asked for were:

1. Fasi source: Page 185. The relevant text related to this COI on that reference page is: "We note that the Paterson–Stockmeyer method is not the fastest known algorithm for evaluating polynomials of matrices: Paterson and Stockmeyer [17] discuss a technique that requires fewer matrix multiplications than the algorithm above, and an alternative approach for reducing the number of matrix multiplications to evaluate polynomials of matrices has recently been proposed by Sastre [18]" (reference [18] from this publication is the main reference [1] cited above)
2. Frommer source: Page 1677. The relevant text related to this COI on that reference page is: "For the special case of polynomials approximating the exponential, approaches which further reduce the number of matrix multiplications were developed in [46, 47, 48]" ([46] is reference [1] cited above).
3. Abdalla source: Page 14. The relevant text related to this COI on that reference page is: "Moreover, more recently many results concerting orthogonal matrix polynomials were introduced (see e.g. [66,68–70])" ([70] is reference [1] cited above).
4. Jarlebring source: Page 33. The relevant text related to this COI on that reference page is: "See Reference [34] for other approaches to evaluate rational approximants with few multiplications and left-divisions.” ([34] is reference [1] cited above).
5. Kubelik source: Page 914. The relevant text related to this COI on that reference page is: "See also modifications of the Paterson–Stockmeyer algorithm in [5, 50]." (reference [50] is reference [1] cited above).

I am sorry but I am confused since I counted 5 references, could you please let me know which one is the sixth one? Thank you Jorge Sastre (talk) 14:42, 14 August 2023 (UTC)

@Jorge Sastre Thank you for your reply. The Frommer’s reference, Abdalla’s reference, Jarlebring’s reference and Kubelik’s reference are not secondary sources. They are additional primary sources studying these concepts. Regards,  Spintendo  16:08, 14 August 2023 (UTC)

@Spintendo Thank you for your help. I need some time for getting the secondary sources and page numbers. Regards Jorge Sastre (talk) 10:09, 17 August 2023 (UTC)

Dear @Spintendo, here some secondary sources for the references you asked:

Frommer's reference:

1. "Computing Enclosures for the Matrix Mittag–Leffler Function" https://doi.org/10.1007/s10915-021-01447-6 , Page 2 text: "There exist many well-established algorithms for enclosing matrix functions (see, e.g., [11,12,13,14,15,16,17,18,19,20,21,22,23])" (Frommer's reference is [20])

2. "Fast verified computation for real powers of large matrices with Kronecker structure", https://doi.org/10.1016/j.amc.2023.128055 Page 1 text: "There are well-established verification algorithms for matrix functions (see [3,4,7–9,16–24] )." (Frommer's reference is [8])

3. "Computing the spectral decomposition of interval matrices and a study on interval matrix powers", https://doi.org/10.1016/j.amc.2021.126174 Page 1 text: "Let us also mention, since it is related to the second part of the paper, that verified spectral decomposition was also applied to verified matrix exponentiation [7,8]." (Frommer's reference is [7])

Abdalla's reference:

1. "A system of Cauchy fractional differential equations and new properties of Mittag-Leffler functions with matrix argument", https://doi.org/10.1016/j.cam.2021.113977 , Page 1 text "Special functions of matrix arguments have been the subject of several studies in the last two decades. A quick glance at the recent literature, whether in statistics, Lie group theory or differential equations immediately shows their abundant appearance. The subject of orthogonal matrix polynomials such as Hermite, Bessel, Laguerre,– also grew up in parallel, with applications in Fourier series expansions, interpolation and quadrature, splines and medical imaging. However, most studies of functions with matrix arguments are devoted to the hypergeometric matrix function [1]" (Abdalla's reference is [1])

2. "Discrete matrix hypergeometric functions", https://doi.org/10.1016/j.jmaa.2022.126716 Page 2 text "The continuous matrix hypergeometric functions were introduced in [14]for p =2and q=1 and generalized to arbitrary pand qin [2,20]" (Abdalla's reference is [2])

Jarlebring's reference:

1. "Parallel Computation of functions of matrices and their action on vectors", https://arxiv.org/abs/2210.03714, Page 12 text In [29] the authors show how to optimise the search of the coefficients in some approximations of functions of matrices that hopefully could be used for this problem too. (Jarlebring's reference is [29])

Kubeliks's reference:

1. "APPROXIMATE FINDING OF THE DIFFERENTIAL OF THE OPERATION OF CALCULATING A MATRIX FUNCTION"

VG Kurbatov, IV Kurbatova - 2023 - vestnik.vsu.ru (in Russian) http://www.vestnik.vsu.ru/pdf/physmath/2023/02/2023-02-08.pdf , Page 70 text Google translation "Earlier in [10], to calculate fr1spA,Bq˛H, the approximation ppA,Bq˛H was used, where p polynomial interpolating fr1s at the zeros of the Chebyshev polynomial. At the same time, additionally it was assumed that the spectra of the matrices A and B are real." (Kubelik's reference is [10])

Thank you Jorge Sastre (talk) 19:08, 23 August 2023 (UTC)

References

 Implemented  Spintendo  19:17, 24 August 2023 (UTC)

Dear @Spintendo, thank you, but the given reference is not the one I gave which proposes the methods more efficient than Paterson-Stockmeyer method. Could you change it? Best regards Jorge Sastre (talk) 07:54, 25 August 2023 (UTC)

I asked for a secondary source which confirmed the information you've proposed. You supplied that secondary source. So the information should be confirmed by that secondary source. If it isn't, please advise, so that I may remove the claim. If, according to you, your source is the only acceptable source, then I'm not prepared to add this information. Regards,  Spintendo  21:28, 30 August 2023 (UTC)

Dear @Spintendo. The best secondary reference is the one saying on its page 185 the following: "We note that the Paterson–Stockmeyer method is not the fastest known algorithm for evaluating polynomials of matrices: Paterson and Stockmeyer [17] discuss a technique that requires fewer matrix multiplications than the algorithm above, and an alternative approach for reducing the number of matrix multiplications to evaluate polynomials of matrices has recently been proposed by Sastre [18]. These algorithms evaluate several appropriately chosen polynomials of lower degree, whose coefficients are obtained from those of the original polynomial by means of various techniques." , ([18] is reference )

Then, could you please change the modification for the following?:

Sastre proposed methods based on matrix polynomial multiplications and additions allowing to save nonscalar matrix multiplications with respect to the Paterson-Stockmeyer method ."

Best regards Jorge Sastre (talk) 13:02, 1 September 2023 (UTC)

 Reference updated.  Spintendo  19:30, 1 September 2023 (UTC)

References