Search

In recent years, several research areas related to tensors (multidimensional matrices) have been exploited, nonlinear optimization, multilinear algebra, nonlinear analysis, statistics, programming language... In the modeling of several phenomena, the tensor representation proves efficiency in front of the matrix one. Indeed, the real data processing from different problems often leading to overwhelming demands on the computer resources (storage, calculation cost...). Convinced of the efficiency of the tonsorial approach, we propose in this thesis, a study that targets the generalization of numerical matrix methods via tonsorial formalism. In particular, we have focused on the extension of the Krylov subspace methods and their applications. More precisely, we have introduced tonsorial global and block Krylov subspace methods related to the various tensor products already existing. We have even succeeded in developing a new class of these methods named tubal Krylov subspace methods. Moreover, we propose applications of these methods in the resolution of linear and nonlinear tensor systems, image and video restoration, as well as the resolution of Sylvester tensor equations. We also deal with methods related to machine learning and facial recognition. In other words, we propose a generalization of the numerical methods of identification and facial recognition: the linear discriminant analysis and the multilinear discriminant analysis via several tensor products. We also develop in this thesis another axis of numerical analysis, " Extrapolation methods". We propose numerical methods based on tensor formalism which generalizes the vector and matrix extrapolation methods., Dans ces dernières années, plusieurs axes de recherches liées aux tenseurs (matrices multidimensionnelles) ont été exploités, optimisation non linéaire, algèbre multilinéaire, analyse non linéaire, statistiques, langage de programmation ... Vu que dans la modélisation de plusieurs phénomènes, la représentation tensorielle a prouvé efficacité face à celle matricielle. En effet, les données réelles traitées à partir des différents problèmes entraînant souvent des demandes écrasantes sur les ressources informatiques (stockage, coût de calcul ...) Convaincus par l’efficacité de l’approche tensorielle, nous proposons dans cette thèse, une étude qui cible la généralisation des méthodes numériques matricielles via le formalisme tensoriel. En particulier, nous nous sommes concentrés sur l’extension des méthodes des sous espaces de Krylov et leurs applications. Plus précisément, nous avons introduit les méthodes de sous espace de Krylov tensorielles, type global et par blocs liés aux différents produits tensoriels existant déjà. Nous avons même réussi à développer une nouvelle catégorie de ces méthodes nommée méthodes des sous espaces de Krylov tubales. De plus, nous avons proposé des applications de ces méthodes dans la résolution des systèmes tensoriels linéaires et non linéaires, la restauration des images et vidéos, ainsi que la résolution des équations tensorielles de Sylvester. Nous traitons aussi les méthodes liées aux machines Learning et la reconnaissance faciale. En d’autres termes, nous proposons une généralisation des méthodes numériques d’identification et reconnaissance faciale, à savoir l’analyse linéaire discriminante et l’analyse multilinéaire discriminantes, via plusieurs produits tensoriels. Nous développons aussi dans cette thèse un autre axe de l’analyse numérique, il s’agit des méthodes d’accélération des suites "L’extrapolation". Nous proposons un ensemble de méthodes numériques basées sur le formalisme tensoriel qui généralisent les méthodes d’extrapolation vectorielles et matricielles.

International audience; JANO’12 is the twelfth edition of the international congress : Days of Numerical Analysis and Optimization. The term JANO comes from the French acronym Journées d’Analyse Numérique et Optimisation. This scientific event, which takes place in Al-Hoceima (Morocco) from 18 to 20 October 2018, is organized by the Mathematics, Approximation and Optimization (MAO) research team of the Laboratory of Applied Sciences (LSA) : a research entity of the National School of Applied Sciences of Al-Hoceima (ENSAH : Ecole Nationale des Sciences Appliquées d’Al-Hoceima) in collaboration with the Faculty of Science and Technology of Al-Hoceima (FSTH : Faculté des Sciences et Techniques), which are two institutions of Abdelmalek Essaadi University. The main objective of this scientific meeting is to bring together researchers from different fields of Applied Mathematics - and more particularly researchers working in the field of numerical analysis, optimization, scientific computation, Data Analysis, Big Data mining and its applications- to contribute to the development of the economic and environmental fields. Participants will present and discuss their latest results in these areas. Thus, the twelfth edition of JANO’12 is an opportunity to discuss a numerous of research topics on recent developments in Applied Mathematics and Computer Sciences. This edition of the meeting follows eleven previous editions which took place in different Moroccan Universities. The main topics of the conference are -but are not limited to-• Numerical Linear Algebra and Applications,• Numerical Analysis and Optimization,• Inverse Problems,• Numerical methods for PDEs, stochastic PDEs,...• Meshless methods based on radial basis function for PDEs,• Stochastical models and Applied Mathematics in Finance area,• Big Data mining and Data Analysis,• Numerical methods for PDEs in image processing. This meeting also aims to strengthen scientific exchanges between the various national and international researchers ; to enable young researchers to promote their scientific work and promote local and national scientific research in the field of applied mathematics and optimization.

Bivariate matrix functions provide a unified framework for various tasks in numerical linear algebra, including the solution of linear matrix equations and the application of the Frechet derivative. In this work, we propose a novel tensorized Krylov subspace method for approximating such bivariate matrix functions and analyze its convergence. While this method is already known for some instances, our analysis appears to result in new convergence estimates and insights for all but one instance, Sylvester matrix equations.

The differential Sylvester equation and its symmetric version, the differential Lyapunov equation, appear in different fields of applied mathematics like control theory, system theory, and model order reduction. The few available straight-forward numerical approaches if applied to large-scale systems come with prohibitively large storage requirements. This shortage motivates us to summarize and explore existing solution formulas for these equations. We develop a unifying approach based on the spectral theorem for normal operators like the Sylvester operator $\mathcal S(X)=AX+XB$ and derive a formula for its norm using an induced operator norm based on the spectrum of $A$ and $B$. In view of numerical approximations, we propose an algorithm that identifies a suitable Krylov subspace using Taylor series and use a projection to approximate the solution. Numerical results for large-scale differential Lyapunov equations are presented in the last sections., 30 pages, 51 figures

We present an iterative method based on the Hermitian and skew-Hermitian splitting HSS for solving the continuous Sylvester equation. By using the HSS of the coefficient matrices A and B, we establish a method which is practically inner/outer iterations, by employing a conjugate gradient on the normal equations CGNR-like method as inner iteration to approximate each outer iterate, while each outer iteration is induced by a convergent splitting of the coefficient matrices. Via this method, a Sylvester equation with coefficient matrices and which are the skew-Hermitian part of A and B, respectively is solved iteratively by a CGNR-like method. Convergence conditions of this method are studied and numerical examples show the efficiency of this method. In addition, we show that the quasi-Hermitian splitting can induce accurate, robust and effective preconditioned Krylov subspace methods.

In the numerical treatment of large-scale Sylvester and Lyapunov equations, projection methods require solving a reduced problem to check convergence. As the approximation space expands, this solution takes an increasing portion of the overall computational effort. When data are symmetric, we show that the Frobenius norm of the residual matrix can be computed at significantly lower cost than with available methods, without explicitly solving the reduced problem. For certain classes of problems, the new residual norm expression combined with a memory-reducing device make classical Krylov strategies competitive with respect to more recent projection methods. Numerical experiments illustrate the effectiveness of the new implementation for standard and extended Krylov subspace methods.

Based on the Hermitian and skew-Hermitian (HS) splitting for non-Hermitian matrices, a nonalternating preconditioned Hermitian and skew-Hermitian splitting-Krylov plus inverted Krylov subspace (NPHSS-KPIK) iteration method for solving a class of large and low-rank complex Sylvester equations arising from the two-dimensional time-periodic fractional diffusion problem is established. The local convergence condition is proposed and the optimal parameter is given. Numerical experiments are used to show the efficiency of the NPHSS-KPIK iteration method for solving the Sylvester equations arising from the time-periodic fractional diffusion equations.

We present a nested splitting conjugate gradient iteration method for solving large sparse continuous Sylvester equation, in which both coefficient matrices are (non-Hermitian) positive semi-definite, and at least one of them is positive definite. This method is actually inner/outer iterations, which employs the Sylvester conjugate gradient method as inner iteration to approximate each outer iterate, while each outer iteration is induced by a convergent and Hermitian positive definite splitting of the coefficient matrices. Convergence conditions of this method are studied and numerical experiments show the efficiency of this method. In addition, we show that the quasi-Hermitian splitting can induce accurate, robust and effective preconditioned Krylov subspace methods.

We consider the numerical approximation to the solution of the matrix equation $A_1 X + X A_2 - Y C =0$ in the unknown matrices $X$, $Y$, under the constraint $XB=0$, with $A_1, A_2$ of large dimensions. We propose a new formulation of the problem that entails the numerical solution of an unconstrained Sylvester equation. The spectral properties of the resulting coefficient matrices call for appropriately designed variants of projection-type methods. To this end, we propose new enriched approximation spaces and provide experimental evidence of their effectiveness on benchmark problems. The application to a control problem is also described.

This paper presents a factorization of the error system that arises in model reduction of linear time invariant systems by Krylov subspace methods. The factorization is introduced for reduced models that match moments and/or Markov parameters of the original system with multiple inputs and outputs. Furthermore, dual results are given for the reduction with input and output Krylov subspaces. To this end, this work constitutes a generalization of [Wolf et al. (2011)] where the factorization was first presented for a special case. The results emerge from an investigation of the Sylvester equations that arise in the context of Krylov subspaces. To that effect, previous results on Sylvester equations are revised and extended in this paper. The theoretic results on Krylov subspaces that are presented here can be useful in error analysis and in the selection of expansion points in Krylov-based model order reduction.

Recently, Ding and Chen [F. Ding, T. Chen, On iterative solutions of general coupled matrix equations, SIAM J. Control Optim. 44 (2006) 2269–2284] developed a gradient-based iterative method for solving a class of coupled Sylvester matrix equations. The basic idea is to regard the unknown matrices to be solved as parameters of a system to be identified, so that the iterative solutions are obtained by applying hierarchical identification principle. In this note, by considering the coupled Sylvester matrix equation as a linear operator equation we give a natural way to derive this algorithm. We also propose some faster algorithms and present some numerical results.

In the present paper, we propose a Krylov subspace method for solving large and sparse generalized Sylvester matrix equations. The proposed method is an iterative projection method onto matrix Krylov subspaces. As a particular case, we show how to adapt the ILU and the SSOR preconditioners for solving large Sylvester matrix equations. Numerical examples and applications to some PDE’s will be given.

The matrix Sylvester equation for congruence, or T-Sylvester equation, has recently attracted considerable attention as a consequence of its close relation to palindromic eigenvalue problems. The theory concerning T-Sylvester equations is rather well understood and there are stable and e cient numerical algorithms which solve these equations for small- to medium-sized matrices. However, developing numerical algorithms for solving large-scale T-Sylvester equations still remains an open problem. In this paper, we present several projection algorithms based on di erent Krylov spaces for solving this problem when the right-hand side of the T-Sylvester equation is a low-rank matrix. The new algorithms have been extensively tested, and the reported numerical results show that they work very well in practice, o ering a clear guidance on which algorithm is the most convenient in each situation. This work has been supported by Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542. Publicado

In this paper we propose minimal residual methods augmented with eigenvectors for solving large Sylvester matrix equations AX + XB = C and generalized Sylvester matrix equations AXB + X = C. The subspace, from which the approximate solution is extracted, is the Kronecker product subspace of two augmented Krylov subspaces. Numerical experiments report the effectiveness of these methods.

This paper presents preconditioned Galerkin and minimal residual algorithms for the solution of Sylvester equations AX-XB=C. Given two good preconditioner matrices M and N for matrices A and B, respectively, we solve the Sylvester equations MAXN-MXBN=MCN. The algorithms use the Arnoldi process to generate orthonormal bases of certain Krylov subspaces and simultaneously reduce the order of Sylvester equations. Numerical experiments show that the solution of Sylvester equations can be obtained with high accuracy by using the preconditioned versions of Galerkin and minimal residual algorithms and this versions are more robust and more efficient than those without preconditioning.

In the present paper, we propose an Arnoldi-based method for solving large and sparse Sylvester matrix equations with low rank right hand sides. We will show how to extract low-rank approximations via a matrix Krylov subspace method. We give some theoretical results such an expression of the exact solution and upper bounds for the norm of the error and for the residual. Numerical experiments will also be given to show the effectiveness of the proposed method.

In the paper we propose Galerkin and minimal residual methods for iteratively solving generalized Sylvester equations of the form AXB − X = C. The algorithms use Krylov subspace for which orthogonal basis are generated by the Arnoldi process and reduce the storage space required by using the structure of the matrix. We give some convergence results and present numerical experiments for large problems to show that our methods are efficient.

This paper presents a new method for obtaining a matrix M which is an approximate inverse preconditioner for a given matrix A, where the eigenvalues of A all either have negative real parts or all have positive real parts. This method is based on the approximate solution of the special Sylvester equation AX + XA = 2I. We use a Krylov subspace method for obtaining an approximate solution of this Sylvester matrix equation which is based on the Arnoldi algorithm and on an integral formula. The computation of the preconditioner can be carried out in parallel and its implementation requires only the solution of very simple and small Sylvester equations. The sparsity of the preconditioner is preserved by using a proper dropping strategy. Some numerical experiments on test matrices from Harwell–Boing collection for comparing the numerical performance of the new method with an available well-known algorithm are presented.

In this paper, we pe a new Divid-and-Conquer type method for the generalized discrete Sylveter equation : AXB + X = C , where the matrices A, B and C are large and sparse, and in addition, B is banded. This matrix equation arises in various applications in science and engineeing. In particular, a special form of the equation, namely, the diete-time Lyapunov equation : AXA T - X + C = 0 arises in important control applications, such as stability analysis, balancing and model reduction. The standard numerical methods, such as the Hessenberg-Schur method, are not suitable for large-scale computing because the sparsity of the data matrices are completely destroyed. In last few years, Arnoldi and Lanczos-based Krylov subspace methods have been developed for large continuous and discrete-time Lyapunov, and continuous-time Sylvester equations. But no such methods have been published yet for the generalized Sylvester equation of the above type. The proposed method is of Divide-and-Conquer type and Arnoldi-basd. Thus it is suitable for both large-scale and parallel computations. The results of our numerical experiments show that the new method gives a satisfactory accuracy on relative residual error norms with several large and sparse test problems. On the other hand, the relative residual errors obtained by the existing Arnoldi-based method for the discrete-Lyapunov equation are not satisfactory at all, even for medium sized problems. More meaningful experiment and analysis with this new method are curntly underway.

In the present paper, we propose block Krylov subspace methods for solving the Sylvester matrix equation AX−XB=C. We first consider the case when A is large and B is of small size. We use block Krylov subspace methods such as the block Arnoldi and the block Lanczos algorithms to compute approximations to the solution of the Sylvester matrix equation. When both matrices are large and the right-hand side matrix is of small rank, we will show how to extract low-rank approximations. We give some theoretical results such as perturbation results and bounds of the norm of the error. Numerical experiments will also be given to show the effectiveness of these block methods.

In this note we analyze the numerical solution ofAX −XB =C when a Galerkin method is applied, assuming thatB has much smaller size thanA. We show that the corresponding Galerkin equation can be obtained from the truncation of the original problem, if matrix polynomials are used for writing the analytical solutionX. Moreover, we provide some relations between the separation ofA andB in their natural space and that in the projected space. Experimental tests validate some of the theoretical results and show the rate of applicability of the method with respect to a standard linear system solver.

We describe Galerkin and minimal residual algorithms for the solution of Sylvester's equation AX – XB = C . The algorithms use Krylov subspaces forwhich orthogonal bases are generated by the Arnoldi process. For certain choices of Krylov subspaces the computation of the solution splits into the solution of many independent subproblems. This makes the algorithms suitable for implementation on parallel computers.

Sylvester equations AX − XB = C play an important role in numerical linear algebra. For example, they arise in the computation of invariant subspaces, in control problems, as linearizations of algebraic Riccati equations, and in the discretization of partial differential equations. For small systems, direct methods are feasible. For large systems, iterative solution methods are available, like Krylov subspace methods. It can be observed that there are essentially two types of subspace methods for Sylvester equations: one in which block matrices are treated as rigid objects (functions on a grid), and one in which the blocks are seen as a basis of a subspace.

In this paper we show how to improve the approximate solution of the large Sylvester equation obtained by an arbitrary method. Such problems appear in many areas of control theory such as the computation of Hankel singular values, model reduction algorithms and others. Moreover, we propose a new method based on refinement process and weighted block Arnoldi algorithm for solving large Sylvester matrix equation. The numerical tests report the effectiveness of these methods.

In this paper, we establish a connection between Krylov subspace techniques for Multipoint Padé interpolation, and the use of Sylvester equations for constructing reduced-order models. We also briefly point out that this connection partly extends to ADI-type techniques and to the Smith iteration for computing approximate solutions of Lyapunov equations.

In this paper we study numerical methods for solving Sylvester matrix equations of the form AX +XBT +CDT = 0. A new projection method is proposed. The union of Krylov subspaces in A and its inverse and the union of Krylov subspaces in B and its inverse are used as the right and left projection subspaces, respectively. The Arnoldi-like process for constructing the orthonormal basis of the projection subspaces is outlined. We show that the approximate solution is an exact solution of a perturbed Sylvester matrix equation. Moreover, exact expression for the norm of residual is derived and results on finite termination and convergence are presented. Some numerical examples are presented to illustrate the effectiveness of the proposed method., {"references":["A. C. Antoulas, Approximation of Large-scale Dynamical Systems,\nSIAM, Philadelphia, PA, 2005.","Z. Bai, D. Day, J. Demmel and J. Dongarra, A Test Matrix Collection\nfor Non-Hermitian Eigenvalue Problems (Release 1.0), Available at\nhttp://www.cs.ucdavis.edu/ bai/NEP/document/collection.ps, 1996.","L. Bao, Y. Lin and Y. Wei, A new projection method for solving large\nSylvester equations, Appl. Numer. Math., 57(2007), 521-532.","R. H. Bartels and G. W. Stewart, Algorithm 432: Solution of the matrix\nequation AX + XB = C, Comm. ACM, 15(1972), 820-826.","U. Baur and P. Benner, Factorized solution of Lyapunov equations based\non hierarchical matrix arithmetic, Computing, 78(2006), 211-234.","U. Baur and P. Benner, Cross-gramian based model reduction for datasparse\nsystems, Tech. rep., Fakult┬¿at f┬¿ur mathematik, TU Chemnitz,\n09107 Chemnitz, FRG, submitted for publication, 2007.","P. Benner, E. S. Quintana-Ort'─▒ and G. Quintana-Ort'─▒, Solving stable\nSylvester equations via rational iterative schemes, J. Sci. Comput.,\n28(2006), 51-83.","P. Benner, R.-C. Li, and N. Truhar, On the ADI method for Sylvester\nequations, preprint.","R. Bhatia and P. Rosenthal, How and why to solve the operator equation\nAX − XB = Y , Bull. London Math. Soc., 29(1997), 1-21.\n[10] A. Bouhamidi, K. Jbilou, Sylvester Tikhonov-regularization methods in\nimage restoration, J. Comput. Appl. Math., 206(2007), 86-98.\n[11] B. N. Datta, Numerical Methods for Linear Control Systems: Design\nand Analysis, Elsevier Academic Press, Amsterdam, 2004.\n[12] J. W. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia,\n1997.\n[13] V. Druskin and L. Knizhnerman, Extended Krylov subspaces: Approximation\nof the matrix square root and related functions, SIAM J. Matrix\nAnal. Appl., 19(1998), 755-771.\n[14] E. de Souza and S. P. Bhattacharyya, Contollability, observability and\nsolution of AX −XB = C, Linear Algebra Appl., 39(1981), 167-188.\n[15] S. C. Eisenstat, H. C. Elman, and M. H. Schultz, Variational iterative\nmethods for nonsymmetric systems of linear equations, SIAM J. Numer.\nAnal., 20(1983), 345-357.\n[16] A. El Guennouni, K. Jbilou and J. Riquet, Krylov subspace methods for\nsolving large Sylvester equations, Numer. Algorithms, 29(2002), 75-96.\n[17] G. H. Golub, S. Nash and C. Van Loan, A Hessenberg-Schur method for\nthe problem AX+XB = C, IEEE Trans. Automat. Control, 24(1979),\n909-913.\n[18] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd edition,\nJohn Hopkins University Press, Baltimore, 1996.\n[19] S. Gugercin, D. C. Sorensen, and A. C. Antoulas, A modified low-rank\nSmith method for large-scale Lyapunov equations, Numer. Algorithms,\n32(2003), 27-55.\n[20] S. J. Hammarling, Numerical solution of the stable non-negative definite\nLyapunov equation, IMA J. Numer. Anal., 2(1982), 303-323.\n[21] J. Z. Hearon, Nonsingular solutions of TA−BT = C, Linear Algebra\nAppl., 16(1997), 57-63.\n[22] N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM,\nSecond Edition, 2002.\n[23] D. Y. Hu and L. Reichel, Krylov-subspace methods for the Sylvester\nequation, Linear Algebra Appl., 172(1992), 283-313.\n[24] I. M. Jaimoukha and E. M. Kasenally, Krylov subspace methods for\nsolving large Lyapunov equations, SIAM J. Numer. Anal., 31(1994),\n227-251.\n[25] K. Jbilou, A. Messaoudi and H. Sadok, Global FOM and GMRES\nalgorithms for matrix equations, Appl. Numer. Math., 31(1999), 49-63.\n[26] K. Jbilou and A. J. Riquet, Projection methods for large Lyapunov matrix\nequations, Linear Algebra Appl., 415(2006), 344-358.\n[27] D. Kressner, Block variants of Hammarling-s method for solving Lyapunov\nequations, ACM Trans. Math. Software, 34(2008), 1-15.\n[28] A. J. Laub, M. T. Heath, C. C. Paige and R. C.Ward, Computation of system\nbalancing transformations and other applications of simultaneous\ndiagonalization algorithms, IEEE Trans. Automat. Control, 32(1987),\n115-122.\n[29] P. Lancaster and M. Tismenetsky, The Theory of Matrices, 2nd edition,\nAcademic Press, Orlando, 1985.\n[30] J.-R. Li and J. White, Low rank solution of Lyapunov equations, SIAM\nJ. Matrix Anal. Appl., 24(2002), 260-280.\n[31] A. Lu and E. Wachspress, Solution of Lyapunov equations by alternating\ndirection implicit iteration, Comput. Math. Appl., 21(1991), 43-58.\n[32] The MathWorks, Inc., MATLAB 7, September 2004.\n[33] T. Penzl, A cyclic low-rank Smith method for large sparse Lyapunov\nequations, SIAM J. Sci. Comput., 21(2000), 1401-1418.\n[34] M. Robbe and M. Sadkane, A convergence analysis of GMRES and FOM\nmethods for Sylvester equations, Numer. Algorithms, 30(2002), 71-84.\n[35] A. Ruhe, Numerical aspects of Gramm-Schmidt orthogonalization of\nvectors, Linear Algebra Appl., 52(1983), 591-601.\n[36] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual\nalgorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist.\nComput., 7(1986), 856-869.\n[37] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edition.,\nSIAM, Philadelphia, 2003.\n[38] V. Simoncini, A new iterative method for solving large-scale Lyapunov\nmatrix equations, SIAM J. Sci. Comput., 29(2007), 1268-1288.\n[39] V. Simoncini and D. B. Szyld, Theory of inexact Krylov subspace\nmethods and applications to scientific computing, SIAM J. Sci. Comput.,\n25(2003), 454-477.\n[40] V. Simoncini and D. B. Szyld, New conditions for non-stagnation of\nminimal residual methods, Numer. Math., 109(2008), 477-487.\n[41] R. Smith, Matrix equation XA + BX = C, SIAM J. Appl. Math.,\n16(1968), pp. 198-201.\n[42] D. C. Sorensen and A. C. Antoulas, The Sylvester equation and\napproximate balanced reduction, Linear Algebra Appl., 352(2002), 671-\n700.\n[43] D. C. Sorensen and Y. Zhou, Direct methods for matrix Sylvester and\nLyapunov equations, J. Appl. Math., 6(2003), 277-303.\n[44] E. Wachspress, Iterative solution of the Lyapunov matrix equation, Appl.\nMath. Lett., 107(1988), 87-90."]}