# Algorithms for simultaneous Hermite–Padé approximations

Johan Rosenkilde, Arne Storjohann

Research output: Contribution to journalJournal articleResearchpeer-review

12 Downloads (Pure)

## Abstract

We describe how to compute simultaneous Hermite–Padé approximations, over a polynomial ring K[x] for a field K using O(nω−1td) operations in K, where d is the sought precision, where n is the number of simultaneous approximations using t<n polynomials, and where O(nω) is the cost of multiplying n×n matrices over K. We develop two algorithms using different approaches. Both algorithms return a reduced sub-basis that generates the complete set of solutions to the input approximation problem that satisfy the given degree constraints. Previously, the cost O(nω−1td) has only been reached with randomized algorithms finding a single solution for the case t<n. Our results are made possible by recent breakthroughs in fast computations of minimal approximant bases and Hermite–Padé approximations for the case t≥n.

Original language English Journal of Symbolic Computation 102 279-303 0747-7171 https://doi.org/10.1016/j.jsc.2019.07.026 Published - 1 Jan 2020

## Keywords

• Approximant bases
• Padé approximation
• Structured linear systems
{"ft_lang_label":"__label__en","ft_lang_prob":0.8195887,"math_prob":0.5580147,"size":1079,"snap":"2021-21-2021-25","text_gpt3_token_len":252,"char_repetition_ratio":0.12837209,"word_repetition_ratio":0.0,"special_character_ratio":0.2150139,"punctuation_ratio":0.055555556,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98620486,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-06-18T19:26:37Z\",\"WARC-Record-ID\":\"<urn:uuid:d1a16886-3497-4d8a-bbe3-4275a2c441f0>\",\"Content-Length\":\"46835\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:73532ffa-7057-49b3-8d59-ba89612e9b29>\",\"WARC-Concurrent-To\":\"<urn:uuid:ec8f7d06-9b59-404c-9447-6c8aa2a0d325>\",\"WARC-IP-Address\":\"34.253.178.11\",\"WARC-Target-URI\":\"https://orbit.dtu.dk/en/publications/algorithms-for-simultaneous-hermitepad%C3%A9-approximations\",\"WARC-Payload-Digest\":\"sha1:FUWSFBGSZ4NYKAUGH3S2AUDBJMS65TIE\",\"WARC-Block-Digest\":\"sha1:46YUUACCYXUDIOOUGR6GT6UWM34DJKKH\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-25/CC-MAIN-2021-25_segments_1623487640324.35_warc_CC-MAIN-20210618165643-20210618195643-00510.warc.gz\"}"}