Search

The inverse scaling and squaring algorithm computes the logarithm of a square matrix $A$ by evaluating a rational approximant to the logarithm at the matrix $B:=A^{2^{-s}}$ for a suitable choice of $s$. We introduce a dual approach and approximate the logarithm of $B$ by solving the rational equation $r(X)=B$, where $r$ is a diagonal Padé approximant to the matrix exponential at $0$. This equation is solved by a substitution technique in the style of those developed by Fasi & Iannazzo (2020, Substitution algorithms for rational matrix equations. Elect. Trans. Num. Anal., 53, 500–521). The new method is tailored to the special structure of the diagonal Padé approximants to the exponential and in terms of computational cost is more efficient than the state-of-the-art inverse scaling and squaring algorithm.

[EN] The most popular method for computing the matrix logarithm is a combination of the inverse scaling and squaring method in conjunction with a Pade approximation, sometimes accompanied by the Schur decomposition. In this work, we present a Taylor series algorithm, based on the free-transformation approach of the inverse scaling and squaring technique, that uses recent matrix polynomial formulas for evaluating the Taylor approximation of the matrix logarithm more efficiently than the Paterson-Stockmeyer method. Two MATLAB implementations of this algorithm, related to relative forward or backward error analysis, were developed and compared with different state-of-the art MATLAB functions. Numerical tests showed that the new implementations are generally more accurate than the previously available codes, with an intermediate execution time among all the codes in comparison., This research was funded by the European Regional Development Fund (ERDF) and the Spanish Ministerio de Economia y Competitividad Grant TIN2017-89314-P.

[EN] Recently, two general methods for evaluating matrix polynomials requiring one matrix product less than the Paterson-Stockmeyer method were proposed, where the cost of evaluating a matrix polynomial is given asymptotically by the total number of matrix product evaluations. An analysis of the stability of those methods was given and the methods have been applied to Taylor-based implementations for computing the exponential, the cosine and the hyperbolic tangent matrix functions. Moreover, a particular example for the evaluation of the matrix exponential Taylor approximation of degree 15 requiring four matrix products was given, whereas the maximum polynomial degree available using Paterson-Stockmeyer method with four matrix products is 9. Based on this example, a new family of methods for evaluating matrix polynomials more efficiently than the Paterson-Stockmeyer method was proposed, having the potential to achieve a much higher efficiency, i.e., requiring less matrix products for evaluating a matrix polynomial of certain degree, or increasing the available degree for the same cost. However, the difficulty of these family of methods lies in the calculation of the coefficients involved for the evaluation of general matrix polynomials and approximations. In this paper, we provide a general matrix polynomial evaluation method for evaluating matrix polynomials requiring two matrix products less than the Paterson-Stockmeyer method for degrees higher than 30. Moreover, we provide general methods for evaluating matrix polynomial approximations of degrees 15 and 21 with four and five matrix product evaluations, respectively, whereas the maximum available degrees for the same cost with the Paterson-Stockmeyer method are 9 and 12, respectively. Finally, practical examples for evaluating Taylor approximations of the matrix cosine and the matrix logarithm accurately and efficiently with these new methods are given., This research was partially funded by the European Regional Development Fund (ERDF) and the Spanish Ministerio de Economia y Competitividad grant TIN2017-89314-P, and by the Programa de Apoyo a la Investigacion y Desarrollo 2018 of the Universitat Politecnica de Valencia grant PAID-06-18-SP20180016.

Deciding whether a Markov matrix is embeddable (i.e. can be written as the exponential of a rate matrix) is an open problem even for $4\times 4$ matrices. We study the embedding problem and rate identifiability for the K80 model of nucleotide substitution. For these $4\times 4$ matrices, we fully characterize the set of embeddable K80 Markov matrices and the set of embeddable matrices for which rates are identifiable. In particular, we describe an open subset of embeddable matrices with non-identifiable rates. This set contains matrices with positive eigenvalues and also diagonal largest in column matrices, which might lead to consequences in parameter estimation in phylogenetics. Finally, we compute the relative volumes of embeddable K80 matrices and of embeddable matrices with identifiable rates. This study concludes the embedding problem for the more general model K81 and its submodels, which had been initiated by the last two authors in a separate work., Comment: 20 pages; 10 figures

Noferini, Vanni/0000-0002-1775-041X; Tisseur, Francoise/0000-0002-1011-2570 WOS:000473026800016 We study the structured condition number of differentiable maps between smooth matrix manifolds, extending previous results to maps that are only R-differentiable for complex manifolds. We present algorithms to compute the structured condition number. As special cases of smooth manifolds, we analyze automorphism groups, and Lie and Jordan algebras associated with a scalar product. For such manifolds, we derive a lower bound on the structured condition number that is cheaper to compute than the structured condition number. We provide numerical comparisons between the structured and unstructured condition numbers for the principal matrix logarithm and principal matrix square root of matrices in automorphism groups as well as for the map between matrices in automorphism groups and their polar decomposition. We show that our lower bound can be used as a good estimate for the structured condition number when the matrix argument is well conditioned. We show that the structured and unstructured condition numbers can differ by many orders of magnitude, thus motivating the development of algorithms preserving structure. Republic of Turkey Ministry of National EducationMinistry of National Education - Turkey; European Research Council Advanced grant MATFUN [267526]; Engineering and Physical Sciences Research CouncilUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/I005293]; Royal Society-Wolfson Research Merit AwardRoyal Society of London The first author's research was supported by the Republic of Turkey Ministry of National Education. The second author's work was partially supported by European Research Council Advanced grant MATFUN (267526). The third author's research was supported by Engineering and Physical Sciences Research Council grant EP/I005293 and by a Royal Society-Wolfson Research Merit Award.

Many quantum information measures can be written as an optimization of the quantum relative entropy between sets of states. For example, the relative entropy of entanglement of a state is the minimum relative entropy to the set of separable states. The various capacities of quantum channels can also be written in this way. We propose a unified framework to numerically compute these quantities using off-the-shelf semidefinite programming solvers, exploiting the approximation method proposed in [Fawzi, Saunderson, Parrilo, Semidefinite approximations of the matrix logarithm, arXiv:1705.00812]. As a notable application, this method allows us to provide numerical counterexamples for a proposed lower bound on the quantum conditional mutual information in terms of the relative entropy of recovery., Comment: 14 pages, v2: minor updates

Constitutive laws in terms of the logarithmic strain tensor log U , i.e. the principal matrix logarithm of the stretch tensor U = F T F corresponding to the deformation gradient F , have been a subject of interest in nonlinear elasticity theory for a long time. In particular, there have been multiple attempts to derive a viable constitutive law of nonlinear elasticity from an elastic energy potential which depends solely on the logarithmic strain measure ‖ log U ‖ 2 , i.e. an energy function W : GL + ( n ) → R of the form (1) W ( F ) = Ψ ( ‖ log U ‖ 2 ) with a suitable function Ψ : [ 0 , ∞ ) → R , where ‖ . ‖ denotes the Frobenius matrix norm and GL + ( n ) is the group of invertible matrices with positive determinant. However, while such energy functions enjoy a number of favorable properties, we show that it is not possible to find a strictly monotone function Ψ such that W of the form (1) is Legendre–Hadamard elliptic. Similarly, we consider the related isochoric strain measure ‖ dev n log U ‖ 2 , where dev n log U is the deviatoric part of log U . Although a polyconvex energy function in terms of this strain measure has recently been constructed in the planar case n = 2 , we show that for n ≥ 3 , no strictly monotone function Ψ : [ 0 , ∞ ) → R exists such that F ↦ Ψ ( ‖ dev n log U ‖ 2 ) is polyconvex or even rank-one convex. Moreover, a volumetric-isochorically decoupled energy of the form F ↦ Ψ ( ‖ dev n log U ‖ 2 ) + W vol ( det F ) cannot be rank-one convex for any function W vol : ( 0 , ∞ ) → R if Ψ is strictly monotone.

There is a one to one mapping between a $p$ dimensional strictly positive definite covariance matrix $\Sigma$ and its matrix logarithm $L$. We exploit this relationship to study the structure induced on $\Sigma$ through a sparsity constraint on $L$. Consider $L$ as a random matrix generated through a basis expansion, with the support of the basis coefficients taken as a simple random sample of size $s=s^{*}$ from the index set $[p(p+1)/2]=\{1,\ldots,p(p+1)/2\}$. We find that the expected number of non-unit eigenvalues of $\Sigma$, denoted $\mathbb{E}[|\mathcal{A}|]$, is approximated with near perfect accuracy by the solution of the equation ¶ \[\frac{4p+p(p-1)}{2(p+1)}[\log (\frac{p}{p-d})-\frac{d}{2p(p-d)}]-s^{*}=0.\] Furthermore, the corresponding eigenvectors are shown to possess only ${p-|\mathcal{A}^{c}|}$ non-zero entries. We use this result to elucidate the precise structure induced on $\Sigma$ and $\Sigma^{-1}$. We demonstrate that a positive definite symmetric matrix whose matrix logarithm is sparse is significantly less sparse in the original domain. This finding has important implications in high dimensional statistics where it is important to exploit structure in order to construct consistent estimators in non-trivial norms. An estimator exploiting the structure of the proposed class is presented.

The matrix logarithm, when applied to Hermitian positive definite matrices, is concave with respect to the positive semidefinite order. This operator concavity property leads to numerous concavity and convexity results for other matrix functions, many of which are of importance in quantum information theory. In this paper we show how to approximate the matrix logarithm with functions that preserve operator concavity and can be described using the feasible regions of semidefinite optimization problems of fairly small size. Such approximations allow us to use off-the-shelf semidefinite optimization solvers for convex optimization problems involving the matrix logarithm and related functions, such as the quantum relative entropy. The basic ingredients of our approach apply, beyond the matrix logarithm, to functions that are operator concave and operator monotone. As such, we introduce strategies for constructing semidefinite approximations that we expect will be useful, more generally, for studying the approximation power of functions with small semidefinite representations., 31 pages, Introduction rewritten and numerous small changes throughout

We consider the two logarithmic strain measures \(\omega _{\mathrm {iso}}= ||{{\mathrm{dev}}}_n \log U ||\) and \(\omega _{\mathrm {vol}}= |{{\mathrm{tr}}}(\log U) |\), which are isotropic invariants of the Hencky strain tensor \(\log U = \log (F^TF)\), and show that they can be uniquely characterized by purely geometric methods based on the geodesic distance on the general linear group \({{\mathrm{GL}}}(n)\). Here, F is the deformation gradient, \(U=\sqrt{F^TF}\) is the right Biot-stretch tensor, \(\log \) denotes the principal matrix logarithm, \(||\,.\, ||\) is the Frobenius matrix norm, \({{\mathrm{tr}}}\) is the trace operator and Open image in new window is the n-dimensional deviator of \(X\in \mathbb {R}^{n\times n}\). This characterization identifies the Hencky (or true) strain tensor as the natural nonlinear extension of the linear (infinitesimal) strain tensor \(\varepsilon ={{\mathrm{sym}}}\nabla u\), which is the symmetric part of the displacement gradient \(\nabla u\), and reveals a close geometric relation between the classical quadratic isotropic energy potential in linear elasticity and the geometrically nonlinear quadratic isotropic Hencky energy. Our deduction involves a new fundamental logarithmic minimization property of the orthogonal polar factor R, where \(F=RU\) is the polar decomposition of F.

We investigate a finite element formulation of the exponentiated Hencky-logarithmic model whose strain energy function is given by $$\begin{aligned} W_\mathrm {eH}(\varvec{F}) = \dfrac{\mu }{k}\, e^{\displaystyle k \left||\text{ dev }_n \log \varvec{U}\right||^2} + \dfrac{\kappa }{2 \hat{k}}\, e^{\displaystyle \hat{k} [\text{ tr } (\log \varvec{U})]^2 }, \end{aligned}$$ where $$\mu >0$$ is the (infinitesimal) shear modulus, $$\kappa >0$$ is the (infinitesimal) bulk modulus, k and $$\hat{k}$$ are additional dimensionless material parameters, $$\varvec{U}=\sqrt{\varvec{F}^T\varvec{F}}$$ is the right stretch tensor corresponding to the deformation gradient $$\varvec{F}$$ , $$\log $$ denotes the principal matrix logarithm on the set of positive definite symmetric matrices, $$\text{ dev }_n \varvec{X} = \varvec{X}-\frac{\text{ tr } \varvec{X}}{n}\varvec{1}$$ and $$||\varvec{X} ||= \sqrt{\text{ tr }\varvec{X}^T\varvec{X}}$$ are the deviatoric part and the Frobenius matrix norm of an $$n\times n$$ -matrix $$\varvec{X}$$ , respectively, and $$\text{ tr }$$ denotes the trace operator. To do so, the equivalent different forms of the constitutive equation are recast in terms of the principal logarithmic stretches by use of the spectral decomposition together with the undergoing properties. We show the capability of our approach with a number of relevant examples, including the challenging “eversion of elastic tubes” problem.

The mathematical model of pseudo-random number generator is given in the paper. The problems of discrete logarithm tasks solving and the concept of «hard bits» for discrete logarithm are considered in the paper. Constraints are imposed related to the absence of logarithm which can compute the discrete logarithm of y = g x mod p , where x ≤ 2 c for polynomial time. The constraint is called the assumption on discrete logarithm with short с bit exponents ( с – DLSE ). As an example, the Sundaram- Patel’s generator is given, qualitative and quantitative characteristics of the generator resistance to the main types of attacks are proposed. The paper gives the analysis of algorithms for generating pseudo-random numbers, such as the algorithm of Blum-Blum- Shub algorithm, Blum-Micali, Fortuna and Yarrow. Based on specified criteria, evaluation of algorithms is given, conclusions on the advantages and disadvantages of each algorithm are made.

A well-known problem in computing some matrix functions iteratively is the lack of a clear, commonly accepted residual notion. An important matrix function for which this is the case is the matrix exponential. Suppose the matrix exponential of a given matrix times a given vector has to be computed. We develop the approach of Druskin, Greenbaum, and Knizhnerman [SIAM J. Sci. Comput., 19 (1998), pp. 38–54] and interpret the sought-after vector as the value of a vector function satisfying the linear system of ordinary differential equations (ODEs) whose coefficients form the given matrix. The residual is then defined with respect to the initial value problem for this ODE system. The residual introduced in this way can be seen as a backward error. We show how the residual can be computed efficiently within several iterative methods for the matrix exponential. This resolves the question of reliable stopping criteria for these methods. Further, we show that the residual concept can be used to construct new residual-based iterative methods. In particular, a variant of the Richardson method for the new residual appears to provide an efficient way to restart Krylov subspace methods for evaluating the matrix exponential.

This article deduces geometric convergence rates for approximating matrix functions via inverse-free rational Krylov methods. In applications one frequently encounters matrix functions such as the matrix exponential or matrix logarithm; often the matrix under consideration is too large to compute the matrix function directly, and Krylov subspace methods are used to determine a reduced problem. If many evaluations of a matrix function of the form f ( A ) v with a large matrix A are required, then it may be advantageous to determine a reduced problem using rational Krylov subspaces. These methods may give more accurate approximations of f ( A ) v with subspaces of smaller dimension than standard Krylov subspace methods. Unfortunately, the system solves required to construct an orthogonal basis for a rational Krylov subspace may create numerical difficulties and/or require excessive computing time. This paper investigates a novel approach to determine an orthogonal basis of an approximation of a rational Krylov subspace of (small) dimension from a standard orthogonal Krylov subspace basis of larger dimension. The approximation error will depend on properties of the matrix A and on the dimension of the original standard Krylov subspace. We show that our inverse-free method for approximating the rational Krylov subspace converges geometrically (for increasing dimension of the standard Krylov subspace) to a rational Krylov subspace. The convergence rate may be used to predict the dimension of the standard Krylov subspace necessary to obtain a certain accuracy in the approximation. Computed examples illustrate the theory developed.

This article has two purposes. Firstly, the article is devoted to collecting basic facts about the Floquet theorem and various Floquet factorisation algorithms claimed for finite-dimensional linear continuous-time periodic (FDLCP) systems. Secondly, the article presents a unified representation framework for various Floquet factorisations in FDLCP systems, while structural and analytic characteristics about them are examined as well. More precisely, the following aspects are considered: (i) algorithms for Floquet factorisations; (ii) characteristics of Floquet factors; (iii) relationships and properties among Floquet factorisations. Most results are reported for the first time, while the others are generalised versions of existing ones.

We consider the two logarithmic strain measures$$\begin{array}{ll} {\omega_{\mathrm{iso}}} = ||{{\mathrm dev}_n {\mathrm log} U} || = ||{{\mathrm dev}_n {\mathrm log} \sqrt{F^TF}}|| \quad \text{ and } \quad \\ {\omega_{\mathrm{vol}}} = |{{\mathrm tr}({\mathrm log} U)} = |{{\mathrm tr}({\mathrm log}\sqrt{F^TF})}| = |{\mathrm log}({\mathrm det} U)|\,,\end{array}$$ωiso=||devnlogU||=||devnlogFTF||andωvol=|tr(logU)=|tr(logFTF)|=|log(detU)|,which are isotropic invariants of the Hencky strain tensor$${\log U}$$logU, and show that they can be uniquely characterized by purely geometric methods based on the geodesic distance on the general linear group$${{\rm GL}(n)}$$GL(n). Here,$${F}$$Fis the deformation gradient,$${U=\sqrt{F^TF}}$$U=FTFis the right Biot-stretch tensor,$${\log}$$logdenotes the principal matrix logarithm,$${\| \cdot \|}$$‖·‖is the Frobenius matrix norm,$${\rm tr}$$tris the trace operator and$${{\text dev}_n X = X- \frac{1}{n} \,{\text tr}(X)\cdot {\mathbb{1}}}$$devnX=X-1ntr(X)·1is the$${n}$$n-dimensional deviator of$${X\in{\mathbb {R}}^{n \times n}}$$X∈Rn×n. This characterization identifies the Hencky (or true) strain tensor as the natural nonlinear extension of the linear (infinitesimal) strain tensor$${\varepsilon={\text sym}\nabla u}$$ε=sym∇u, which is the symmetric part of the displacement gradient$${\nabla u}$$∇u, and reveals a close geometric relation between the classical quadratic isotropic energy potential$$\mu {\| {\text dev}_n {\text sym} \nabla u \|}^2 + \frac{\kappa}{2}{[{\text tr}({\text sym} \nabla u)]}^2 = \mu {\| {\text dev}_n \varepsilon \|}^2 + \frac{\kappa}{2} {[{\text tr} (\varepsilon)]}^2$$μ‖devnsym∇u‖2+κ2[tr(sym∇u)]2=μ‖devnε‖2+κ2[tr(ε)]2in linear elasticity and the geometrically nonlinear quadratic isotropic Hencky energy$$\mu {\| {\text dev}_n log U \|}^2 + \frac{\kappa}{2}{[{\text tr}(log U)]}^2 = \mu {\omega_{{\text iso}}^2} + \frac{\kappa}{2}{\omega_{{\text vol}}^2},$$μ‖devnlogU‖2+κ2[tr(logU)]2=μωiso2+κ2ωvol2,where$${\mu}$$μis the shear modulus and$${\kappa}$$κdenotes the bulk modulus. Our deduction involves a new fundamental logarithmic minimization property of the orthogonal polar factor$${R}$$R, where$${F=RU}$$F=RUis the polar decomposition of$${F}$$F. We also contrast our approach with prior attempts to establish the logarithmic Hencky strain tensor directly as the preferred strain tensor in nonlinear isotropic elasticity.

A new matrix function corresponding to the scalar unwinding number of Corless, Hare, and Jeffrey is introduced. This matrix unwinding function, $\mathcal{U}$, is shown to be a valuable tool for deriving identities involving the matrix logarithm and fractional matrix powers, revealing, for example, the precise relation between $\log A^\alpha$ and $\alpha \log A$. The unwinding function is also shown to be closely connected with the matrix sign function. An algorithm for computing the unwinding function based on the Schur--Parlett method with a special reordering is proposed. It is shown that matrix argument reduction using the function $\mathrm{mod}(A) = A-2\pi i\, \mathcal{U}(A)$, which has eigenvalues with imaginary parts in the interval $(-\pi,\pi]$ and for which $\e^A = \e^{\mathrm{mod}(A)}$, can give significant computational savings in the evaluation of the exponential by scaling and squaring algorithms.

The unitary polar factor $Q=U_p$ in the polar decomposition of $Z=U_p \, H$ is the minimizer over unitary matrices $Q$ for both $\|{\rm Log}(Q^* Z)\|^2$ and its Hermitian part $\|{{\rm sym}{_{_*}}\!}({\rm Log}(Q^* Z))\|^2$ over both $\mathbb{R}$ and $\mathbb{C}$ for any given invertible matrix $Z\in\mathbb{C}^{n\times n}$ and any matrix logarithm Log, not necessarily the principal logarithm log. We prove this for the spectral matrix norm for any $n$ and for the Frobenius matrix norm for $n\leq 3$. The result shows that the unitary polar factor is the nearest orthogonal matrix to $Z$ not only in the normwise sense but also in a geodesic distance. The derivation is based on Bhatia's generalization of Bernstein's trace inequality for the matrix exponential and a new sum of squared logarithms inequality. Our result generalizes the fact for scalars that for any complex logarithm and for all $z\in\mathbb{C}{\setminus}\{0\} \min_{\vartheta\in(-\pi,\pi]}{|{\rm Log}_{\mathbb{C}}(e^{-i\vartheta} z)|}^2={|{\rm log}|...

The isotropic Hencky strain energy appears naturally as a distance measure of the deformation gradient to the set SO ( n ) of rigid rotations in the canonical left-invariant Riemannian metric on the general linear group GL ( n ) . Objectivity requires the Riemannian metric to be left- GL ( n ) -invariant, isotropy requires the Riemannian metric to be right- O ( n ) -invariant. The latter two conditions are only satisfied for a three-parameter family of Riemannian metrics on the tangent space of GL ( n ) . Surprisingly, the final result is basically independent of the chosen parameters. In deriving the result, geodesics on GL ( n ) have to be parameterized and a novel minimization problem, involving the matrix logarithm for non-symmetric arguments, has to be solved.

We show that the unitary factor Up in the polar decomposition of a nonsingular matrix Z=UpH is a minimizer for both ‖Log(Q⁎Z)‖and‖sym⁎(Log(Q⁎Z))‖ over the unitary matrices Q∈U(n) for any given invertible matrix Z∈Cn×n, for any unitarily invariant norm and any n. We prove that Up is the unique matrix with this property to minimize all these norms simultaneously. As important tools we use a generalized Bernstein trace inequality and the theory of majorization.

We continue our study on the elliptic curve discrete logarithm problem over finite extension fields. We show, among others, the following results: For sequences of prime powers (qi)i∈ℕ and natural numbers (ni)i∈ℕ with ni→∞ and ni∕log(qi)2→0 for i→∞, the discrete logarithm problem in the groups of rational points of elliptic curves over the fields Fqini can be solved in subexponential expected time (qini)o(1). Let a, b>0 be fixed. Then the problem over fields Fqn, where q is a prime power and n a natural number with a⋅ log(q)1∕3≤n≤b⋅ log(q), can be solved in an expected time of eO(log(qn)3∕4).

A popular method for computing the matrix logarithm is the inverse scaling and squaring method, which essentially carries out the steps of the scaling and squaring method for the matrix exponential in reverse order. Here we make several improvements to the method, putting its development on a par with our recent version [SIAM J. Matrix Anal. Appl., 31 (2009), pp. 970-989] of the scaling and squaring method for the exponential. In particular, we introduce backward error analysis to replace the previous forward error analysis; obtain backward error bounds in terms of the quantities ||A p|| 1/p, for several small integer p, instead of ||A||; and use special techniques to compute the argument of the Padé approximant more accurately. We derive one algorithm that employs a Schur decomposition, and thereby works with triangular matrices, and another that requires only matrix multiplications and the solution of multiple right-hand side linear systems. Numerical experiments show the new algorithms to be generally faster and more accurate than their existing counterparts and suggest that the Schur-based method is the method of choice for computing the matrix logarithm. © 2012 Society for Industrial and Applied Mathematics.

We introduce the method of path-sums which is a tool for exactly evaluating a function of a discrete matrix with possibly non-commuting entries, based on the closed-form resummation of infinite families of terms in the corresponding Taylor series. If the matrix is finite, our approach yields the exact result in a finite number of steps. We achieve this by combining a mapping between matrix powers and walks on a weighted directed graph with a universal graph-theoretic result on the structure of such walks. We present path-sum expressions for a matrix raised to a complex power, the matrix exponential, matrix inverse, and matrix logarithm. We show that the quasideterminants of a matrix can be naturally formulated in terms of a path-sum, and present examples of the application of the path-sum method. We show that obtaining the inversion height of a matrix inverse and of quasideterminants is an NP-complete problem., 23 pages, light version submitted to SIAM Journal on Matrix Analysis and Applications (SIMAX). A separate paper with the graph theoretic results is available at: arXiv:1202.5523v1. Results for matrices over division rings will be published separately as well

A new algorithm is developed for computing arbitrary real powers $A^p$ of a matrix $A\in\mathbb{C}^{n\times n}$. The algorithm starts with a Schur decomposition, takes $k$ square roots of the triangular factor $T$, evaluates an $[m/m]$ Pad\'e approximant of $(1-x)^p$ at $I - T^{1/2^k}$, and squares the result $k$ times. The parameters $k$ and $m$ are chosen to minimize the cost subject to achieving double precision accuracy in the evaluation of the Pad\'e approximant, making use of a result that bounds the error in the matrix Pad\'e approximant by the error in the scalar Pad\'e approximant with argument the norm of the matrix. The Pad\'e approximant is evaluated from the continued fraction representation in bottom-up fashion, which is shown to be numerically stable. In the squaring phase the diagonal and first superdiagonal are computed from explicit formulae for $T^{p/2^j}$, yielding increased accuracy. Since the basic algorithm is designed for $p\in(-1,1)$, a criterion for reducing an arbitrary real $p$ to this range is developed, making use of bounds for the condition number of the $A^p$ problem. How best to compute $A^k$ for a negative integer $k$ is also investigated. In numerical experiments the new algorithm is found to be superior in accuracy and stability to several alternatives, including the use of an eigendecomposition and approaches based on the formula $A^p = \exp(p\log(A))$.

We consider the valued field $\mathds{K}:=\mathbb{R}((\Gamma))$ of formal series (with real coefficients and monomials in a totally ordered multiplicative group $\Gamma>$). We investigate how to endow $\mathds{K}$ with a logarithm $l$, which satisfies some natural properties such as commuting with infinite products of monomials. In the article "Hardy type derivations on generalized series fields", we study derivations on $\mathds{K}$. Here, we investigate compatibility conditions between the logarithm and the derivation, i.e. when the logarithmic derivative is the derivative of the logarithm. We analyse sufficient conditions on a given derivation to construct a compatible logarithm via integration of logarithmic derivatives. In her monograph "Ordered exponential fields", the first author described the exponential closure $\mathds{K}^{\rm{EL}}$ of $(\mathds{K},l)$. Here we show how to extend such a log-compatible derivation on $\mathds{K}$ to $\mathds{K}^{\rm{EL}}$., Comment: 25 pages

Generalized polar decomposition method (or briefly GPD method) has been introduced by Munthe-Kaas and Zanna to approximate the matrix exponential. In this paper, we investigate the numerical stability of that method with respect to roundoff propagation. The numerical GPD method includes two parts: splitting of a matrix $Z\in \mathfrak{g}$, a Lie algebra of matrices and computing $\exp(Z)\mathbf{v}$ for a vector $\mathbf{v}$. We show that the former is stable provided that $\|Z\|$ is not so large, while the latter is not stable in general except with some restrictions on the entries of the matrix Z and the vector $\mathbf{v}$.

The statistical analysis of covariance matrix data is considered and, in particular, methodology is discussed which takes into account the non-Euclidean nature of the space of positive semi-definite symmetric matrices. The main motivation for the work is the analysis of diffusion tensors in medical image analysis. The primary focus is on estimation of a mean covariance matrix and, in particular, on the use of Procrustes size-and-shape space. Comparisons are made with other estimation techniques, including using the matrix logarithm, matrix square root and Cholesky decomposition. Applications to diffusion tensor imaging are considered and, in particular, a new measure of fractional anisotropy called Procrustes Anisotropy is discussed., Published in at http://dx.doi.org/10.1214/09-AOAS249 the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

In this paper we give bounds for the error arising in the approximation of the logarithm of a block triangular matrix T by Padé approximants of the function f(x)=log[(1+x)/(1-x)] and partial sums of Gregory's series. These bounds show that if the norm of all diagonal blocks of the Cayley-transform B=(T-I)(T+I)-1 is sufficiently close to zero, then both approximation methods are accurate. This will contribute for reducing the number of successive square roots of T needed in the inverse scaling and squaring procedure for the matrix logarithm. http://www.sciencedirect.com/science/article/B6TYD-4G5BJ9P-2/1/398a212a906943d2474a2cd6166c1d31

In this paper the formula of the exponential matrix e A when A is a semi skew-symmetric real matrix of order 4 is derived. The formula is a generalization of the Rodrigues formula for skew-symmetric matrices of order 3 in Minkowski 3-space.

We present an explicit polynomial formula for evaluating the principal logarithm of all matrices lying on the line segment $\{I(1-t)+At:t\in [0,1]\}$ joining the identity matrix $I$ (at $t=0$) to any real matrix $A$ (at $t=1$) having no eigenvalues on the closed negative real axis. This extends to the matrix logarithm the well known Putzer's method for evaluating the matrix exponential., 6 pages

An implicit purification scheme is proposed for calculation of the temperature-dependent, grand canonical single-particle density matrix, given as a Fermi operator expansion in terms of the Hamiltonian. The computational complexity is shown to scale with the logarithm of the polynomial order of the expansion, or equivalently, with the logarithm of the inverse temperature. The system of linear equations that arise in each implicit purification iteration is solved efficiently by a conjugate gradient solver. The scheme is particularly useful in connection with linear scaling electronic structure theory based on sparse matrix algebra. The efficiency of the implicit temperature expansion technique is analyzed and compared to some explicit purification methods for the zero temperature density matrix., 4 pages, 2 figures

We propose a new analytic formula for evaluating the derivatives of a matrix exponential. In contrast to the diagonalization method, eigenvalues and eigenvectors do not appear explicitly in the derivation, although we show that a necessary and sufficient condition for the validity of the formula is that the matrix has distinct eigenvalues. The new formula expresses the derivatives of a matrix exponential in terms of minors, polynomials, the exponential of the matrix as well as matrix inversion, and hence is algebraically more manageable. For sparse matrices, the formula can be further simplified. Two examples are discussed in some detail. For the companion matrix of a continuous-time autoregress\-ive moving average process, the derivatives of the exponential of the companion matrix can be computed recursively. The second example concerns the exponential of the tri\-diagonal transition intensity matrix of a finite-state-space continuous-time Markov chain whose instantaneous transitions must be between adjacent states. We present a numerical study to show that the new method may yield numerically more accurate results than the diagonalization method, at the expense of a slight increase in computation.

For a sequence of independent identically distributed Euclidean random vectors, we prove a law of the iterated logarithm for the sample covariance matrix when $o(\log \log n)$ terms are omitted. The result is proved under the hypothesis that the random vectors belong to the generalized domain of attraction of the multivariate Gaussian law. As an application, we obtain a bounded law of the iterated logarithm for the multivariate t-statistic.

We show that for a vast class of matrix Lie groups, which includes the orthogonal and the symplectic, diagonal Padé approximants of log((1+x)/(1-x)) are structure preserving. The conditioning of these approximants is analyzed. We also present a new algorithm for the Briggs-Padé method, based on a strategy for reducing the number of square roots in the inverse scaling and squaring procedure. http://www.sciencedirect.com/science/article/B6V0R-439WFRV-4/1/a3695a33e70aef2dd31f867ef9c1c8fc

The matrix exponential plays a very important role in many fields of mathematics and physics. It can be computed by many methods. This work is devoted to the study of some explicit formulas for computing eA, where A is a special square matrix. The main results are based on the convergent power series of eA. Examples and applications are given.

The distance rstab(A) of a stable matrix A to the set of unstable matrices and the norm of the exponential of matrices constitute two important topics in stability theory. We treat in this note the case of large matrices. The method proposed partitions the matrix into two blocks: a small block in which the stability is studied and a large block whose field of values is located in the complex plane. Using the information on the blocks and some results on perturbation theory, we give sufficient conditions for the stability of the original matrix, a lower bound of rstab(A) and an upper bound on the norm of the exponential of A. We illustrate these theoretical bounds on a practical test problem.

This paper deals with a direct derivation of Fisher's information matrix of vector state space models for the general case, by which is meant the establishment of the matrix as a whole and not element by element. The method to be used is matrix differentiation, see [4]. We assume the model to be Gaussian and use the negative logarithm of the likelihood function as used in the definition of Fisher's information. In a related paper Klein et al. [3] establish the information matrix by assembling its elements as derived in the literature [2,5,6] and for an approximation of the Hessian of the log-likelihood function one can refer to [7,8].

Some low dimension or low rank cases of a formula for a product of exponentials of matrices are studied using eigenvalue considerations. Counterexamples to certain natural conjectures involving a product of matrix exponentials are also given, and comments relating to certain recently discovered exponential identities are included.

Sufficient conditions for the law of the iterated logarithm for non-degenerate U-processes are presented. The law of the iterated logarithm for V-C subgraph classes of functions is obtained under second moment of the envelope. A bracketing condition for the law of the iterated logarithm for U-processes is presented. Applications to the law of the iterated logarithm of U-statistics with estimated parameters and M-estimators are mentioned.

In this paper we explore the computation of the matrix exponential in a manner that is consistent with Lie group structure. Our point of departure is the decomposition of Lie algebra as the semidirect product of two Lie subspaces and an application of the Baker–Campbell–Hausdorff formula. Our results extend the results in Iserles and Zanna (2005) [2], Zanna and Munthe-Kaas(2001/02) [4] to a range of Lie groups: the Lie group of all solid motions in Euclidean space, the Lorentz Lie group of all solid motions in Minkowski space and the group of all invertible (upper) triangular matrices. In our method, the matrix exponential group can be computed by a less computational cost and is more accurate than the current methods. In addition, by this method the approximated matrix exponential belongs to the corresponding Lie group.

Some function space laws of the iterated logarithm for Brownian motion with values in finite and infinite dimensional vector spaces are shown to follow from Hincin's classical law of the iterated logarithm and some martingale techniques. A law of the iterated logarithm for Brownian motion in a differentible manifold is also stated.