# What is the Time Complexity of the Matrix Exponential?

While trying to compute the Matrix Exponential of an nxn array I decided to take advantage of a Python function called scipy.linalg.expm().

According to the documentation, this function adopts the Pade' Approximant to perform a calculation that, otherwise, is said to require a lot of resources and is still a matter of discussion in the mathematics community.

The documentation itself references a work by Al-Mohy and Higham (doi: 10.1137/04061101X), in which I was not able to find any indication regarding the Time Complexity (either T or Theta would work) of this procedure.

Has anyone come across the same problem? What is your suggestion for determining said Time Complexity?

• Do you want exact outputs or approximate outputs? ​ If exact, then how simplified must the entries be? ​ If approximate, then in what sense? ​ ​ ​ ​ – user12859 May 17 '16 at 11:30
• Uh...well if I understand what you say, the Pade approximation itself returns approximated values. If I don't understand, well, could you be more specific? – FaCoffee May 17 '16 at 11:33
• Should the approximations be ​ ​ ​ absolute , ​ entrywise relative , relative to the operator norm , the algorithm's choice of [absolute / reactive to the operator norm] , simultaneously absolute and relative to the operator norm , entrywise in both absolute and relative error , the algorithm chooses absolute or relative for each entry ​ ​ ​ or something else? ​ ​ ​ ​ ​ ​ ​ ​ – user12859 May 17 '16 at 11:41
• let's go with absolute – FaCoffee May 17 '16 at 11:45