New algorithms for the matrix exponential and its Fréchet derivative are presented. First, we derive a new scaling and squaring algorithm (denoted expm[new]) for computing eA, where A is any square matrix, that mitigates the overscaling problem. The algorithm is built on the algorithm of Higham [SIAM J.Matrix Anal. Appl., 26(4): 1179-1193, 2005] but improves on it by two key features. The first, specific to triangular matrices, is to compute the diagonal elements in the squaring phase as exponentials instead of powering them. The second is to base the backward error analysis that underlies the algorithm on members of the sequence {||Ak||1/k} instead of ||A||. The terms ||Ak||1/k are estimated without computing powers of A by using a matrix 1-norm estimator. Second, a new algorithm is developed for computing the action of the matrix exponential on a matrix, etAB, where A is an n x n matrix and B is n x n₀ with n₀ << n. The algorithm works for any A, its computational cost is dominated by the formation of products of A with n x n₀ matrices, and the only input parameter is a backward error tolerance. The algorithm can return a single matrix etAB or a sequence etkAB on an equally spaced grid of points tk. It uses the scaling part of the scaling and squaring method together with a truncated Taylor series approximation to the exponential. It determines the amount of scaling and the Taylor degree using the strategy of expm[new].Preprocessing steps are used to reduce the cost of the algorithm. An important application of the algorithm is to exponential integrators for ordinary differential equations. It is shown that the sums of the form $\sum_{k=0}^p\varphi_k(A)u_k$ that arise in exponential integrators, where the $\varphi_k$ are related to the exponential function, can be expressed in terms of a single exponential of a matrix of dimension $n+p$ built by augmenting $A$ with additional rows and columns. Third, a general framework for simultaneously computing a matrix function, $f(A)$, and its Fréchet derivative in the direction $E$, $L_f(A,E)$, is established for a wide range of matrix functions. In particular, we extend the algorithm of Higham and $\mathrm{expm_{new}}$ to two algorithms that intertwine the evaluation of both $e^A$ and $L(A,E)$ at a cost about three times that for computing $e^A$ alone. These two extended algorithms are then adapted to algorithms that simultaneously calculate $e^A$ together with an estimate of its condition number. Finally, we show that $L_f(A,E)$, where $f$ is a real-valued matrix function and $A$ and $E$ are real matrices, can be approximated by $\Im f(A+ihE)/h$ for some suitably small $h$. This approximation generalizes the complex step approximation known in the scalar case, and is proved to be of second order in $h$ for analytic functions $f$ and also for the matrix sign function. It is shown that it does not suffer the inherent cancellation that limits the accuracy of finite difference approximations in floating point arithmetic. However, cancellation does nevertheless vitiate the approximation when the underlying method for evaluating $f$ employs complex arithmetic. The complex step approximation is attractive when specialized methods for evaluating the Fréchet derivative are not available.

The heart is one the most important organs in the human body and many other live creatures. The electrical activity in the heart controls the heart function, and many heart diseases are linked to the abnormalities in the electrical activity in the heart. Mathematical equations and computer simulation can be used to model the electrical activity in the heart. The heart models are challenging to solve because of the complexity of the models and the huge size of the problems. Several cell models have been proposed to model the electrical activity in a single heart cell. These models must be coupled with a heart model to model the electrical activity in the entire heart. The bidomain model is a popular model to simulate the propagation of electricity in myocardial tissue. It is a continuum-based model consisting of non-linear ordinary differential equations (ODEs) describing the electrical activity at the cellular scale and a system of partial differential equations (PDEs) describing propagation of electricity at the tissue scale. Because of this multi-scale, ODE/PDE structure of the model, splitting methods that treat the ODEs and PDEs in separate steps are natural candidates as numerical methods. First, we need to solve the problem at the cellular scale using ODE solvers. One of the most popular methods to solve the ODEs is known as the Rush-Larsen (RL) method. Its popularity stems from its improved stability over integrators such as the forward Euler (FE) method along with its easy implementation. The RL method partitions the ODEs into two sets: one for the gating variables, which are treated by an exponential integrator, and another for the remaining equations, which are treated by the FE method. The success of the RL method can be understood in terms of its relatively good stability when treating the gating variables. However, this feature would not be expected to be of benefit on cell models for which the stiffness is not captured by the gating equations. We demonstrate that this is indeed the case on a number of stiff cell models. We further propose a new partitioned method based on the combination of a first-order generalization of the RL method with the FE method. This new method leads to simulations of stiff cell models that are often one or two orders of magnitude faster than the original RL method. After solving the ODEs, we need to use bidomain solvers to solve the bidomain model. Two well-known, first-order time-integration methods for solving the bidomain model are the semi-implicit method and the Godunov operator-splitting method. Both methods decouple the numerical procedure at the cellular scale from that at the tissue scale but in slightly different ways. The methods are analyzed in terms of their accuracy, and their relative performance is compared on one-, two-, and three-dimensional test cases. As suggested by the analysis, the test cases show that the Godunov method is significantly faster than the semi-implicit method for the same level of accuracy, specifically, between 5 and 15 times in the cases presented. Second-order bidomain solvers can generally be expected to be more effective than first-order bidomain solvers under normal accuracy requirements. However, the simplest and the most commonly applied second-order method for the PDE step, the Crank-Nicolson (CN) method, may generate unphysical oscillations. We investigate the performance of a two-stage, L-stable singly diagonally implicit Runge-Kutta method for solving the PDEs of the bidomain model and present a stability analysis. Numerical experiments show that the enhanced stability property of this method leads to more physically realistic numerical simulations compared to both the CN and Backward Euler (BE) methods.

Pour réaliser des simulations précises aux temps longs pour des vagues non linéaires, il faut faire appel à des algorithmes d’évolution temporelle précis. En particulier, la combinaison d’un pas de temps adaptatif avec un facteur intégrant est connue pour être très efficace. Nous proposons une modification de cette technique. Le principe consiste à soustraire un certain polynôme à une EDP. Puis, comme pour le facteur intégrant, nous faisons un changement de variable pour retirer la partie linéaire. Mais nous espérons retirer quelque chose de plus afin de rendre l’EDP moins raide pour les calculs numériques. Le polynôme choisi est une expansion de Taylor autour du temps initial de la solution. Afin de calculer les différentes dérivées nécessaires, nous utilisons le Dense Output qui donne la possibilité d’approximer les dérivées de la solution à tout temps. Une fois le facteur intégrant modifié appliqué, nous faisons appel à une avance temporelle classique afin de résoudre l’équation d’évolution. Il a été considéré plusieurs schémas de Runge-Kutta avec pas de temps adaptatif. Nous avons tiré avantage des méthodes emboîtées, afin de ne pas calculer de nouvelles fonctions et perdre du temps de calcul, en utilisant uniquement des données déjà calculées durant l’évolution temporelle. Les résultats numériques montrent que l’efficacité de notre méthode varie selon les cas. Par exemple, nous avons vérifié que plus le profil de l’onde est pentue, plus notre méthode est efficace. Pour le modèle de vagues non linéaires le plus compliqué à notre disposition, le modèle HOS, nous avons pu réduire le nombre de pas de temps de calcul jusqu’à près de 30 % avec un schéma de Runge-Kutta de Dormand-Prince et jusqu’à plus de 99 % pour un schéma de Bogacki-Shampine. / Efficient time stepping algorithms are crucial for accurate long time simulations of nonlinear waves. In particular, adaptive time stepping combined with an integrating factor are known to be very effective. We propose a modification of the existing technique. The trick consists in subtracting a certain-order polynomial to a PDE. Then, like for the integrating factor, a change of variables is performed to remove the linear part. But, here, we hope to remove something more to make the PDE less stiff to numerical resolution. The polynomial is chosen as a Taylor expansion around the initial time of the solution. In order to calculate the different derivatives, we use a dense output which gives a possibility to approximate the derivatives of the solution at any time. The modified integrating factor being applied, a classical time-stepping method can be used to solve the remaining equation. We focus on various Runge-Kutta schemes with a varying step size. We take advantage of embedded methods and use an evolved adaptive step control. We do not need to calculate new functions and loose time of calculation only by using already estimated values during the temporal evolution. Numerical tests show that the actual efficiency of the method varies along cases. For example, we verified that steeper waves profiles give rise to better behaviour of the method. For fully nonlinear water wave simulations with the HOS model, we can save up to 30% of total time steps with a Dormand-Prince Runge-Kutta scheme and we can save up to 99% with the Bogacki-Shampine scheme.