Search

In this paper we give the detailed error analysis of two algorithms (denoted as $W_1$ and $W_2$) for computing the symplectic factorization of a symmetric positive definite and symplectic matrix $A \in \mathbb R^{2n \times 2n}$ in the form $A=LL^T$, where $L \in \mathbb R^{2n \times 2n}$ is a symplectic block lower triangular matrix. Algorithm $W_1$ is an implementation of the $HH^T$ factorization from [Dopico et al., 2009]. Algorithm $W_2$, proposed in [Bujok et al., 2023], uses both Cholesky and Reverse Cholesky decompositions of symmetric positive definite matrix blocks that appear during the factorization. We prove that Algorithm $W_2$ is numerically stable for a broader class of symmetric positive definite matrices $A \in \mathbb R^{2n \times 2n}$, producing the computed factors $\tilde L$ in floating-point arithmetic with machine precision $u$, such that $||A-\tilde L {\tilde L}^T||_2= {\cal O}(u ||A||_2)$. However, Algorithm $W_1$ is unstable in general for symmetric positive definite and symplectic matrix $A$. This was confirmed by numerical experiments in [Bujok et al., 2023]. In this paper we give corresponding bounds also for Algorithm $W_1$ that are weaker, since we show that the factorization error depends on the size of the inverse of the principal submatrix $A_{11}$. The tests performed in MATLAB illustrate that our error bounds for considered algorithms are reasonably sharp., Comment: 24 pages, 3 figures, 2 tables

We analyze two algorithms for computing the symplectic $LL^T$ factorization $A=LL^T$ of a given symmetric positive definite symplectic matrix $A$. The first algorithm $W_1$ is an implementation of the $HH^T$ factorization from [Dopico et al., 2009], see Theorem 5.2. The second one, algorithm $W_2$ uses both Cholesky and Reverse Cholesky decompositions of symmetric positive definite matrices. We presents a comparison of these algorithms and illustrate their properties by numerical experiments in MATLAB. A particular emphasis is given on simplecticity properties of the computed matrices in floating-point arithmetic.

We find all explicit involutive solutions $X \in \mathbb C^{n \times n}$ of the Yang-Baxter-like matrix equation $AXA=XAX$, where $A \in \mathbb C^{n \times n}$ is a given involutory matrix. The construction is algorithmic.

A real quadratic matrix is generalized doubly stochastic (g.d.s.) if all of its row sums and column sums equal one. We propose numerically stable methods for generating such matrices having possibly orthogonality property or/and satisfying Yang-Baxter equation (YBE). Additionally, an inverse eigenvalue problem for finding orthogonal generalized doubly stochastic matrices with prescribed eigenvalues is solved here. The tests performed in \textsl{MATLAB} illustrate our proposed algorithms and demonstrate their useful numerical properties., Comment: 20 pages

We describe several methods of constructing R-matrices that are dependent upon many parameters, for example unitary R-matrices and R-matrices whose entries are functions. As an application, we construct examples of R-matrices with prescribed singular values. We characterise some classes of indecomposable set-theoretic solutions of the quantum Yang-Baxter equation (QYBE) and construct R-matrices related to such solutions. In particular, we establish a correspondence between one-generator braces and indecomposable, non-degenerate involutive set-theoretic solutions of the QYBE, showing that such solutions are abundant. We show that R-matrices related to involutive, non-degenerate solutions of the QYBE have special form. We also investigate some linear algebra questions related to R-matrices., Comment: Corrected typos and improved presentation

Stability analysis of Wilkinson's iterative refinement with a relaxation IR(omega) for solving linear systems is given. It extends existing results for omega=1, i.e., for Wilkinson's iterative refinement. We assume that all computations are performed in fixed (working) precision arithmetic. Numerical tests were done in MATLAB to illustrate our theoretical results. A particular emphasis is given on convergence of iterative refinement with a relaxation. Our tests confirm that the choice omega=1 is the best choice from the point of numerical stability., Comment: 12 pages

This paper provides error analyses of the algorithms most commonly used for the evaluation of the Chebyshev polynomial of the first kind $T_N(x)$. Some of these algorithms are shown to be backward stable. This means that the computed value of $T_N(x)$ in floating point arithmetic by these algorithms can be interpreted as a slightly perturbed value of polynomial $T_N$, for slightly perturbed value of $x$.

Saddle point problems arise in many important practical applications. In this paper we propose and analyze some algorithms for solving symmetric saddle point problems which are based upon the block Gram-Schmidt method. In particular, we prove that the algorithm BCGS2 (Reorthogonalized Block Classical Gram-Schmidt) using Householder Q-R decomposition implemented in floating point arithmetic is backward stable, under a mild assumption on the matrix $M$. This means that the computed vector $\tilde z$ is the exact solution to a slightly perturbed linear system of equations $Mz = f$.

A new reorthogonalized block classical Gram--Schmidt algorithm is proposed that factorizes a full column rank matrix $A$ into $A=QR$ where $Q$ is left orthogonal (has orthonormal columns) and $R$ is upper triangular and nonsingular. With appropriate assumptions on the diagonal blocks of $R$, the algorithm, when implemented in floating point arithmetic with machine unit $\macheps$, produces $Q$ and $R$ such that $\| I- Q^{T} Q \|_2 =O(\macheps)$ and $\| A-QR \|_2 =O(\macheps \| A \|_2)$. The resulting bounds also improve a previous bound by Giraud et al. [Num. Math., 101(1):87-100,\ 2005] on the CGS2 algorithm originally developed by Abdelmalek [BIT, 11(4):354--367,\ 1971]. \medskip Keywords: Block matrices, Q--R factorization, Gram-Schmidt process, Condition numbers, Rounding error analysis., Comment: 19 pages

An error analysis result is given for classical Gram--Schmidt factorization of a full rank matrix $A$ into $A=QR$ where $Q$ is left orthogonal (has orthonormal columns) and $R$ is upper triangular. The work presented here shows that the computed $R$ satisfies $\normal{R}=\normal{A}+E$ where $E$ is an appropriately small backward error, but only if the diagonals of $R$ are computed in a manner similar to Cholesky factorization of the normal equations matrix. A similar result is stated in [Giraud at al, Numer. Math. 101(1):87--100,2005]. However, for that result to hold, the diagonals of $R$ must be computed in the manner recommended in this work., Comment: 12 pages This v2. v1 (from 2006) has not the biliographical reference set (at all). This is the only modification between v1 and v2. If you want to quote this paper, please quote the version published in Numerische Mathematik

The scheme of divided differences is widely used in many approximation and interpolation problems. Computing the Newton coefficients of the interpolating polynomial is the first step of the Bj\"{o}rck and Pereyra algorithm for solving Vandermonde systems of equations (Cf. \cite{bjorck: 70}). Very often this algorithm produces very accurate solution. The problem of determining the Newton coefficients is intimately related with the problem of evaluation the Lagrange interpolating polynomial, which can be realized by many algorithms. For these reasons we use the uniform approach and analyze also Aitken's algorithm of the evaluation of an interpolating polynomial. We propose new algorithms that are always numerically stable with respect to perturbation in the function values and more accurate than the Aitken's algorithm and the scheme of divided differences, even for complex data., Comment: 19 pages, 4 figures

It is known that Goertzel's algorithm is much less numerically accurate than the Fast Fourier Transform (FFT)(Cf. \cite{gen:69}). In order to improve accuracy we propose modifications of both Goertzel's and Horner's algorithms based on the divide-and-conquer techniques. The proof of the numerical stability of these two modified algorithms is given. The numerical tests in Matlab demonstrate the computational advantages of the proposed modifications. The appendix contains the proof of numerical stability of Goertzel's algorithm of polynomial evaluation., Comment: 22 pages, 3 figures, presented on the GAMM Meeting, Brunschweig, September 2003