Search

Hessenberg matrices frequently arise in many application areas and have been attracted much attention in recent years. In the current paper, we present two numerical algorithms of $$O(n^2)$$ for computing the determinant of an n-by-n general Hessenberg matrix. The algorithms are all suited for implementation using Computer Algebra Systems such as MATLAB and MAPLE. Some numerical examples are provided in order to demonstrate the performance of the proposed algorithms.

It is a challenging work to design a blind color image watermarking scheme for protecting copyright, which is different from the existing schemes used binary image or grayscale image as watermark and is also different from other non-blind watermarking schemes. In this paper, we analyze the feature of the upper Hessenberg matrix, and propose a blind color image watermarking scheme using upper Hessenberg matrix of Hessenberg transform. Arnold transform is used to improve the security, and the MD5-based Hash pseudo-random algorithm is also used to improve the robustness. In the process of watermark embedding, the encrypted watermark information is embedded into the biggest energy element of the Hessenberg matrix by quantization technique. In the process of watermark extraction, the watermark is extracted from the attacked host image with blind manner. Simulation results show that the proposed scheme outperforms other related methods in the aspects of the invisibility, robustness, capacity and computational complexity.

We show that an infinite lower Hessenberg matrix generates polynomial sequences that correspond to the rows of infinite lower triangular invertible matrices. Orthogonal polynomial sequences are obtained when the Hessenberg matrix is tridiagonal. We study properties of the polynomial sequences and their corresponding matrices which are related to recurrence relations, companion matrices, matrix similarity, construction algorithms, and generating functions. When the Hessenberg matrix is also Toeplitz the polynomial sequences turn out to be of interpolatory type and we obtain additional results. For example, we show that every nonderogative finite square matrix is similar to a unique Toeplitz-Hessenberg matrix.

We develop two fast algorithms for Hessenberg reduction of a structured matrix $A = D + UV^H$ where $D$ is a real or unitary $n \times n$ diagonal matrix and $U, V \in\mathbb{C}^{n \times k}$. The proposed algorithm for the real case exploits a two--stage approach by first reducing the matrix to a generalized Hessenberg form and then completing the reduction by annihilation of the unwanted sub-diagonals. It is shown that the novel method requires $O(n^2k)$ arithmetic operations and it is significantly faster than other reduction algorithms for rank structured matrices. The method is then extended to the unitary plus low rank case by using a block analogue of the CMV form of unitary matrices. It is shown that a block Lanczos-type procedure for the block tridiagonalization of $\Re(D)$ induces a structured reduction on $A$ in a block staircase CMV--type shape. Then, we present a numerically stable method for performing this reduction using unitary transformations and we show how to generalize the sub-diagonal elimination to this shape, while still being able to provide a condensed representation for the reduced matrix. In this way the complexity still remains linear in $k$ and, moreover, the resulting algorithm can be adapted to deal efficiently with block companion matrices., 25 pages

Thompson's partition of a cyclic subnormal operator into normal and completely non-normal components is combined with a non-commutative calculus for hyponormal operators for separating outliers from the cloud, in rather general point distributions in the plane. The main result provides exact transformation formulas from the power moments of the prescribed point distribution into the moments of the uniform mass carried by the cloud. The proposed algorithm solely depends on the Hessenberg matrix associated to the original data. The robustness of the algorithm is reflected by the insensitivity of the output under trace class, or by a theorem of Voiculescu, under certain Hilbert-Schmidt class, additive perturbations of the Hessenberg matrix.

[EN] The Combined matrix of a nonsingular matrix A is defined by phi(A)=A T where degrees means the Hadamard (entrywise) product. If the matrix A describes the relation between inputs and outputs in a multivariable process control, phi(A) describes the relative gain array (RGA) of the process and it defines the Bristol method (IEEE Trans Autom Control 1:133-134, 1966) often used for Chemical processes (McAvoy in Interaction analysis: principles and applications. Instrument Society of America, Pittsburgh, 1983; Papadourakis et al. in Ind Eng Chem Res 26(6):1259-1262, 1987; Wang et al. in Chem Eng Technol, 10.1002/ceat.201500202, 2016; Kariwala et al. in Ind Eng Chem Res 45(5):1751-1757, 10.1021/ie050790r, 2006; Golender et al. in J Chem Inf Comput Sci 21(4):196-204, 10.1021/ci00032a004, 1981). The combined matrix has been studied in several works such as Bru et al. (J Appl Math, 10.1155/2014/182354, 2014), Fiedler and Markham (Linear Algebra Appl 435:1945-1955, 2011) and Johnson and Shapiro (SIAM J Algebraic Discrete Methods 7:627-644, 1986). Since phi(A)=(cij) has the property of Sigma kcik=Sigma kckj=1,i,j, when phi(A)>= 0, phi(A) is a doubly stochastic matrix. In certain chemical engineering applications a diagonal of the RGA in wchich the entries are near 1 is used to determine the pairing of inputs and outputs for further design analysis. Applications of these matrices can be found in Communication Theory, related with the satellite-switched time division multiple-access systems, and about a doubly stochastic automorphism of a graph. In this paper we present new algorithms to generate doubly stochastic matrices with the Combined matrix using Hessenberg matrices in Sect.3 and orthogonal/unitary matrices in Sect.4. In addition, we discuss what kind of doubly stochastic matrices are obtained with our algorithms and the possibility of generating a particular doubly stochastic matrix by the map phi., This work has been supported by Spanish Ministerio de Economia y Competitividad Grants MTM2014-58159-P, MTM2017-85669-P and MTM2017-90682-REDT.

Submitted by INÁCIO (ilda@ubi.pt) on 2020-02-05T15:26:12Z No. of bitstreams: 1 Convertible_subspaces_that_arise_from_different_nu.pdf: 293026 bytes, checksum: c89ce7175e26f9cac3aeea5b94435c7f (MD5) Approved for entry into archive by Pessoa (pfep@ubi.pt) on 2020-02-05T17:18:49Z (GMT) No. of bitstreams: 1 Convertible_subspaces_that_arise_from_different_nu.pdf: 293026 bytes, checksum: c89ce7175e26f9cac3aeea5b94435c7f (MD5) Rejected by Pessoa (pfep@ubi.pt), reason: Quando tiver contratualizações com os editores e o documento não possa estar em Acesso Aberto poderá escolher duas modalidades de acesso: Acesso Fechado (sem data de termino) e Acesso Embargado (com data de termino do embargo). Não escolha Acesso restrito. Nestas duas ultimas situações é obrigatório que coloque a JUSTIFICAÇÃO do tipo de acesso e o EMAIL do autor. Siga o nosso Manual de Auxilio ao Autodepósito: https://www.ubi.pt/Ficheiros/Sites/7/Documentos/1375/Instruções%20para%20Auto%20depósito%20de%20documentos.pdf (questões do Acesso na pagina 9). Após corrigir é só submeter de novo. Obrigado on 2020-02-05T17:20:44Z (GMT) Submitted by INÁCIO (ilda@ubi.pt) on 2020-02-05T17:28:14Z No. of bitstreams: 1 Convertible_subspaces_that_arise_from_different_nu.pdf: 293026 bytes, checksum: c89ce7175e26f9cac3aeea5b94435c7f (MD5) Approved for entry into archive by Pessoa (pfep@ubi.pt) on 2020-02-06T11:36:38Z (GMT) No. of bitstreams: 1 Convertible_subspaces_that_arise_from_different_nu.pdf: 293026 bytes, checksum: c89ce7175e26f9cac3aeea5b94435c7f (MD5) Rejected by Pessoa (pfep@ubi.pt), reason: Quando tiver contratualizações com os editores e o documento não possa estar em Acesso Aberto poderá escolher duas modalidades de acesso: Acesso Fechado (sem data de termino) e Acesso Embargado (com data de termino do embargo). NÃO escolha Acesso Restrito. Nestas duas ultimas situações (Embargado e Fechado) é obrigatório que coloque a JUSTIFICAÇÃO do tipo de acesso e o EMAIL do autor. Siga o nosso Manual de Auxilio ao Autodepósito: https://www.ubi.pt/Ficheiros/Sites/7/Documentos/1375/Instruções%20para%20Auto%20depósito%20de%20documentos.pdf (questões do Acesso na pagina 9). Após corrigir é só submeter de novo. Obrigado on 2020-02-06T11:38:18Z (GMT) Submitted by INÁCIO (ilda@ubi.pt) on 2020-02-06T12:10:45Z No. of bitstreams: 1 Convertible_subspaces_that_arise_from_different_nu.pdf: 293026 bytes, checksum: c89ce7175e26f9cac3aeea5b94435c7f (MD5) Approved for entry into archive by Pessoa (pfep@ubi.pt) on 2020-02-07T09:42:12Z (GMT) No. of bitstreams: 1 Convertible_subspaces_that_arise_from_different_nu.pdf: 293026 bytes, checksum: c89ce7175e26f9cac3aeea5b94435c7f (MD5) Approved for entry into archive by Pessoa (pfep@ubi.pt) on 2020-02-07T09:49:32Z (GMT) No. of bitstreams: 1 Convertible_subspaces_that_arise_from_different_nu.pdf: 293026 bytes, checksum: c89ce7175e26f9cac3aeea5b94435c7f (MD5) Made available in DSpace on 2020-02-07T09:49:32Z (GMT). No. of bitstreams: 1 Convertible_subspaces_that_arise_from_different_nu.pdf: 293026 bytes, checksum: c89ce7175e26f9cac3aeea5b94435c7f (MD5) Previous issue date: 2019 info:eu-repo/semantics/publishedVersion

The Neumann expansion of Bessel functions (of integer order) of a function \(g:\mathbb {C}\rightarrow \mathbb {C}\) corresponds to representing g as a linear combination of basis functions φ0, φ1, …, i.e., \(g(s)=\sum _{\ell = 0}^\infty w_\ell \varphi _\ell (s)\), where φi(s) = Ji(s), i = 0, …, are the Bessel functions. In this work, we study an expansion for a more general class of basis functions. More precisely, we assume that the basis functions satisfy an infinite dimensional linear ordinary differential equation associated with a Hessenberg matrix, motivated by the fact that these basis functions occur in certain iterative methods. A procedure to compute the basis functions as well as the coefficients is proposed. Theoretical properties of the expansion are studied. We illustrate that non-standard basis functions can give faster convergence than the Bessel functions.

We present a new method for solving linear systems of the form (A-σI)x=B with large number of complex shifts σ and multiple right- hand sides, designed to run on a hybrid CPU-GPU platform in a highly parallel fashion. Numerical experiments demonstrate benefits of the proposed method in applications, e.g., in control theory when computing the transfer function of a system, or as a part of an algorithm performing interpolatory model reduction (IRKA). This is joint work with Nela Bosner and Zlatko Drmač.

Matris kavramı, bilim dünyasında yoğun olarak kullanılmaktadır. Bu kavram aynı zamanda graf teori, sayılar teorisi, diferensiyel denklemler gibi matematiğin de hemen hemen her alanında çok büyük öneme sahiptir. Bu tez altı ana bölümden oluşmaktadır. Birinci bölümde sayılar ve sayı dizileri, matris kavramı ve graf teori ile ilgili temel tanım ve özellikler verilmiştir. Ardından tezde kullanılan kaynaklar ile ilgili bilgiler verilmiştir. İkinci bölümde k-tridiagonal k-Toeplitz matrisler tanımlanmış, ardından bu matrislerin determinant, permanent ve özdeğerleri için formüller elde edilmiştir. Üçüncü bölümde alt k-Hessenberg Toeplitz matrisler tanımlanmış, ardından bu matrislerin determinantı ve tersleri elde edilmiştir. Dördüncü bölümde genelleştirilmiş balancing ve Lucas-balancing sayı dizileri tanımlanmış, daha sonra bu sayı dizileri ile ilgili özdeşlikler elde edilmiştir. Bunun yanı sıra özel k-tridiagonal matrisler tanımlanıp, bu matrislerin determinant ve permanent değerleri bu sayı dizilerinin kuvvetleri cinsinden elde edilmiştir. Beşinci bölümde yeni bir graf ailesi tanımlanmış, ardından hafnian fonksiyonu yardımıyla bu graf ailesinin mükemmel eşleme sayısı elde edilmiştir. Daha sonra bu graf ailesinin bazı özel alt aileleri için mükemmel eşleme sayılarının iyi bilinen sayı dizilerinin elemanlarına eşit olduğu gösterilmiş ve bu özel alt graf ailelerinin enerjileri için eşitlik, Laplacian enerjileri için üst sınır elde edilmiştir. Son bölümde ise tezde elde edilen sonuçlar ve öneriler tartışılmıştır., Matrix concept is intensively used a many area in science. This concept has also a great importance in almost every field of mathematics such as graph theory, number theory, differential equations. The thesis contains six main sections. In the first section, basic and fundamental definitions and properties relating numbers, number sequences, matrix algebra and graph theory and then, informations about the references in the thesis are given. In the second section, k-tridiagonal k-Toeplitz matrices are defined and then, some formulas for determinant, permanent and eigenvalues of this matrix family are obtained. In the third section, lower k-Hessenberg Toeplitz matrices are defined and an algorithm for determinants and inverses of this matrices are obtained. In the fourth section, generalized balancing and Lucas-balancing number sequences are defined and then, some identities for these number sequences are obtained. Also, it is shown that determinants and permanents of some k-tridiagonal matrices is the powers of these numbers. In the fifth section, a new graph family are introduced and then, the eigenvalues of the adjacency and the Laplacian matrix of this graph family are obtained. Moreover, it is shown that the perfect matching number of this graph family equals to special second order recurrence by hafnian method. For some special kinds of this family, it is obtained that the perfect matching number of corresponding graphs equals to some famous number sequences. Also, identities for energies and upper bounds for Laplacian energies of these special graphs are obtained. The final section discusses the results obtained in the thesis with suggestions.

We characterize Hessenberg matrices D associated with measures in the unit circle ν, which are matrix representations of compact and actually Hilbert Schmidt perturbations of the forward shift operator as those with recursion coefficients urn:x wiley:mma:media:mma5716:mma5716-math-0001 verifying urn:x-wiley:mma:media:mma5716:mma5716-math-0002, ie, associated with measures verifying Szego condition. As a consequence, we obtain the following dichotomy result for Hessenberg matrices associated with measures in the unit circle: either D=SR+K2 with K2, a Hilbert Schmidt matrix, or there exists an unitary matrix U and a diagonal matrix Λ such that urn:x-wiley:mma:media:mma5716:mma5716-math-0003 with K2, a Hilbert Schmidt matrix. Moreover, we prove that for 1 ≤ p ≤ 2, if urn:x-wiley:mma:media:mma5716:mma5716-math-0004, then D=SR+Kp with Kp an absolutely p summable matrix inducing an operator in the p Schatten class. Some applications are given to classify measures on the unit circle.

The classical boundary element method (BEM) is widely used to obtain detailed information on the acoustic performance of large-scale dynamical systems due to the nature of semi-analytical characteristic. Its use, however, results in asymmetric and dense system matrix, which makes original full-order model evaluation very time consuming and memory demanding. Moreover, the frequency sweep analysis which is indispensable for the assessment of noise emission levels and the design of high-quality products requires the repetitive assembly and solution of system of equations, which further increases the computational complexity. In order to alleviate these problems, an adaptive structure-preserving model order reduction method is presented, which is based on an offline–online solution framework. In the offline phase, we first factor out the frequency term as a scalar function from the BE integral kernels of the Burton–Miller formulation, followed by integration to set up the system matrices. A global frequency-independent orthonormal basis is then constructed via the second-order Arnoldi (SOAR) method to span a projection subspace, onto which the frequency-decoupled system matrices are projected column by column to solve the memory problem arising from the frequency-related decomposition. In addition, the number of iterations required for convergence can be automatically determined by exploiting the condition number of an upper Hessenberg matrix in SOAR. In the online stage, a reliable reduced-order model can be quickly recovered by the sum of those offline stored reduced matrices multiplied by frequency-dependent coefficients, which is favored in many-query applications. Two academic benchmarks and a more realistic problem are investigated in order to demonstrate the potentials of the proposed approach.

We derive some sum formulas for the squares of Pell and Pell-Lucas numbers. We construct Hankel-Hessenberg andToeplitz-Hessenberg matrices whose entries in the first column are HHP = aij , ij i j a P = ; Q HH =   ij a , ij i j a Q =and P TH =   ij a , 1 = ij i j a P ; Q TH =   ij a , 1 = ij i j a Q , respectively where n P and n Q denote the usual Pell and Pell-Lucas numbers. Then, we found upper and lower bounds for spectral norm of these matrices.

The analysis of any Hessenberg matrix as a product of a companion matrix and a triangular matrix is presented in this paper. The factors are explicitly given on terms of the entries of the Hessenberg matrix and, further, various factorizations are undertaken. Applications to comrade and confederate matrices, as well as for the corresponding block cases, are included.

Finite representations of the partition function in terms of powers and eigenvalues of a sparse upper Hessenberg matrix are established. The trace of this matrix also yields finite representations of the divisor function. Several identities between partition numbers and other quantities such as matrix functions are derived.

We present a novel algorithm to perform the Hessenberg reduction of an n × n matrix A of the form A = D + U V ⁎ where D is diagonal with real entries and U and V are n × k matrices with k ≤ n . The algorithm has a cost of O ( n 2 k ) arithmetic operations and is based on the quasiseparable matrix technology. Applications are shown to solving polynomial eigenvalue problems and some numerical experiments are reported in order to analyze the stability of the approach.

Matrices A of order n having entries in the field F ( x 1 , … , x n ) of rational functions over a field F and characteristic polynomial det ⁡ ( t I − A ) = t n + x 1 t n − 1 + ⋯ + x n − 1 t + x n are studied. It is known that such matrices are irreducible and have at least 2 n − 1 nonzero entries. Such matrices with exactly 2 n − 1 nonzero entries are called Ma–Zhan matrices. Conditions are given that imply that a Ma–Zhan matrix is similar via a monomial matrix to a generalized companion matrix (that is, a lower Hessenberg matrix with ones on its superdiagonal, and exactly one nonzero entry in each of its subdiagonals). Via the Ax–Grothendieck Theorem (respectively, its analog for the reals) these conditions are shown to hold for a family of matrices whose entries are complex (respectively, real) polynomials.

The fractional diffusion equation is discretized by an implicit finite difference scheme with the shifted Grunwald formula, which is unconditionally stable. The coefficient matrix of the discretized linear system is equal to the sum of the identity matrix with two diagonal-times-Toeplitz matrices. In this paper, the alternating direction implicit (ADI)-like method based on the classical ADI iteration is proposed to solve the discretized linear system. Theoretical analyses show that the ADI-like iteration method is convergent. Each iteration of this method requires the solutions of two linear systems with Hessenberg coefficient matrices. These two systems can be solved effectively by Hessenberg LU factorization. Numerical examples are presented to illustrate the effectiveness of the ADI-like iteration method.

It is well known that every real or complex square matrix is unitarily similar to an upper Hessenberg matrix. The purpose of this paper is to provide a constructive proof of the result that every square matrix polynomial can be reduced to an upper Hessenberg matrix, whose entries are rational functions and in special cases polynomials. It will be shown that the determinant is preserved under this transformation, and both the finite and infinite eigenvalues of the original matrix polynomial can be obtained from the upper Hessenberg matrix.

Digital watermarking has been widely utilized for ownership protection of multimedia contents. This paper introduces a blind symmetric audio watermarking algorithm based on parametric Slant-Hadamard transform (PSHT) and Hessenberg decomposition (HD). In our proposed algorithm, at first watermark image is preprocessed to enhance the security. Then, host signal is divided into non-overlapping frames and the samples of each frame are reshaped into a square matrix. Next, PSHT is performed on each square matrix individually and a part of this transformed matrix of size m&times, m is selected and HD is applied to it. Euclidean normalization is calculated from the 1st column of the Hessenberg matrix, which is further used for embedding and extracting the watermark. Simulation results ensure the imperceptibility of the proposed method for watermarked audios. Moreover, it is demonstrated that the proposed algorithm is highly robust against numerous attacks. Furthermore, comparative analysis substantiates its superiority among other state-of-the-art methods.

The exponential orthogonal polynomials encode via the theory of hyponormal operators a shade functiongsupported by a bounded planar shape. We prove under natural regularity assumptions that these complex polynomials satisfy a three term relation if and only if the underlying shape is an ellipse carrying uniform black on white. More generally, we show that a finite term relation among these orthogonal polynomials holds if and only if the first row in the associated Hessenberg matrix has finite support. This rigidity phenomenon is in sharp contrast with the theory of classical complex orthogonal polynomials. On function theory side, we offer an effective way based on the Cauchy transforms ofg,z̅g,…,z̅dg, to decide whether a (d+ 2)-term relation among the exponential orthogonal polynomials exists; in that case we indicate how the shade functiongcan be reconstructed from a resulting polynomial of degreedand the Cauchy transform ofg. A discussion of the relevance of the main concepts in Hele-Shaw dynamics completes the article.

The inverses of Toeplitz-Hessenberg matrices are investigated. It is known that each inverse of such a matrix is a sum of a lower triangular matrix $L$ and a matrix $R$ of rank $1$. The formulas of $L$ and $x$, $y$ such that $xy^T = R$ are derived. Using this result we propose an algorithm for inverting Toeplitz-Hessenberg matrices. Moreover, from the expression of the inverse a formula for the determinant is deduced.

In this paper we revisit the problem of performing a QR step on an unreduced Hessenberg matrix H when we know an ``exact"" eigenvalue \lambda 0 of H. In exact arithmetic, this eigenvalue will appear on the diagonal of the transformed Hessenberg matrix H\~ and will be decoupled from the remaining part of the Hessenberg matrix, thus resulting in a deflation. But it is well known that in finite-precision arithmetic the so-called perfect shift can get blurred and that the eigenvalue \lambda 0 can then not be deflated and/or is perturbed significantly. In this paper, we develop a new strategy for computing such a QR step so that the deflation is almost always successful. We also show how to extend this technique to double QR steps with complex conjugate shifts

Not every positive functional defined on bi-variate polynomials of a prescribed degree bound is represented by the integration against a positive measure. We isolate a couple of conditions filling this gap, either by restricting the class of polynomials to harmonic ones, or imposing the vanishing of a defect indicator. Both criteria offer constructive cubature formulas and they are obtained via well known matrix analysis techniques involving either the dilation of a contractive matrix to a unitary one or the specific structure of the Hessenberg matrix associated to the multiplier by the underlying complex variable., To appear in Proc. Amer. Math. Soc

This paper proposes a combination of a hybrid CPU--GPU and a pure GPU software implementation of a direct algorithm for solving shifted linear systems $(A-\sigma I)X=B$ with a large number of complex shifts $\sigma$ and multiple right-hand sides. Such problems often appear, e.g., in control theory when evaluating the transfer function, or as a part of an algorithm performing interpolatory model reduction, as well as when computing pseudospectra and structured pseudospectra, or solving large linear systems of ordinary differential equations. The proposed algorithm first jointly reduces the general full $n\times n$ matrix $A$ and the $n\times m$ full right-hand side matrix $B$ to the controller Hessenberg canonical form that facilitates efficient solution: $A$ is transformed to a so-called $m$-Hessenberg form, and $B$ is made upper triangular. This is implemented as a blocked highly parallel CPU--GPU hybrid algorithm ; individual blocks are reduced by the CPU, and the necessary updates of the rest of the matrix are split among the cores of the CPU and the GPU. To enhance parallelization, the reduction and the updates are overlapped. In the next phase, the reduced $m$-Hessenberg--triangular systems are solved entirely on the GPU, with shifts divided into batches. The benefits of such load distribution are demonstrated by numerical experiments. In particular, we show that our proposed implementation provides an excellent basis for efficient implementations of computational methods in systems and control theory, from evaluation of transfer function to the interpolatory model reduction.

We study an isospectral flow (Lax flow) that provides an explicit deformation from upper Hessenberg complex matrices to normal matrices, extending to the complex case and to the case of normal matrices the results of [2] . The Lax flow is given by d A d t = [ [ A † , A ] d u , A ] , where brackets indicate the usual matrix commutator, [ A , B ] : = A B − B A , A † is the conjugate transpose of A and the matrix [ A † , A ] d u is the matrix equal to [ A † , A ] along diagonal and upper triangular entries and zero below diagonal. We prove that if the initial condition A 0 is an upper Hessenberg matrix with simple spectrum, then lim t → + ∞ ⁡ A ( t ) exists and it is a normal upper Hessenberg matrix isospectral to A 0 and if the spectrum of A 0 is contained in a line in the complex plane, then the ω-limit set is actually a tridiagonal normal matrix. Furthermore, we show that this flow is also the solution of an infinite time horizon optimal control problem and we prove that it can be used to construct even dimensional real skew-symmetric tridiagonal matrices with given simple spectrum, and with given signs pattern for the codiagonal elements.

After a concise survey, the expanded Ikebe algorithm for inverting the lower half plus the superdiagonal of an n × n unreduced upper Hessenberg matrix H is extended to general nonsingular upper Hessenberg matrices by computing, in the reduced case, a block diagonal form of the factor matrix HL in the inverse factorization H - 1 = H L U - 1 . This factorization enables us to propose hybrid and accurate (nongaussian) procedures for computing H - 1 . Thus, HL is computed directly in the aim to be used as a fine initial guess for Newton's iteration, which converges to H - 1 in a suitable number of iterations.

Block GMRES is one of the most popular algorithms for solving large non-Hermitian linear systems with multiple right-hand sides. The simpler block GMRES algorithm is a variation of block GMRES, which avoids the factorization of a block upper Hessenberg matrix; and it is much simpler to program and requires less work than block GMRES. However, theoretical results given in this paper indicate that it is less stable due to the ill-conditioning of the basis used. In order to overcome this difficulty, we propose an adaptive simpler block GMRES algorithm for large linear systems with multiple right-hand sides. Theoretical analysis is made to show the reason why the new algorithm is superior to its original counterpart. Moreover, we consider how to restart and precondition the adaptive simpler block GMRES algorithm, and propose a flexible and adaptive simpler block GMRES algorithm with deflated restarting. Numerical experiments show the numerical behavior of our new algorithm.

Here a known result on the structure of finite Hessenberg matrices is extended to infinite Hessenberg matrices. Its consequences for the example of infinite Hessenberg-Toeplitz matrices are described. The results are applied also to the inversion of infinite tridiagonal matrices via recurrence relations. Moreover, since there are available free parameters, different inverses can be associated with a given invertible tridiagonal matrix.

In this note, we define the generalized Fibonacci-Narayana sequence {Gn(a,b,c)}n?N. After that, we derive some relations between these sequences, and permanents and determinants of one type of upper Hessenberg matrix.

The purpose of this note is to extend in a simple and unified way the known results on interlacing of zeros of paraorthogonal polynomials on the unit circle. These polynomials can be regarded as the characteristic polynomials of any matrix similar to an unitary upper Hessenberg matrix with positive subdiagonal elements.

International Conference on Numerical Analysis and Applied Mathematics (ICNAAM) -- SEP 19-25, 2016 -- Rhodes, GREECE, WOS: 000410159800310, In this paper, we study the Padovan numbers and obtain some relationships between this sequence and permanent and determinant of a type of Hessenberg matrices.

In this paper, we will present various results on computing of wide classes of Hessenberg matrices whose entries are the terms of any sequence. We present many new results on the subject as well as our results will cover and generalize earlier many results by using generating function method. Moreover, we will present a new approach on computing Hessenberg determinants, whose entries are general higher order linear recursions with arbitrary constant coefficients, based on finding an adjacency-factor matrix. We will give some interesting showcases to show how to use our new method.

A unitary symplectic similarity transformation for a special class of Hamiltonian matrices to extended Hamiltonian Hessenberg form is presented. Whereas the classical Hessenberg form links to Krylov subspaces, the extended Hessenberg form links to extended Krylov subspaces. The presented algorithm generalizes thus the classic reduction to Hamiltonian Hessenberg form and offers more freedom in the choice of Hamiltonian condensed forms, to be used within an extended Hamiltonian QR algorithm. Theoretical results identifying the structure of the extended Hamiltonian Hessenberg form and proofs of uniqueness of the reduction process are included. Numerical experiments confirm the validity of the approach.

Today, modern developments in science and technology require ever larger dimensional mathematical models. They pose challenging mathematical tasks, that can be tackled using modern numerical methods implemented on state of the art hardware and software tools. Nevertheless, the models may be still to large for numerical simulations, and there is a need for reduction of their dimension. For instance, in case of the LTI dynamical system \begin{; ; equation}; ; \label{; ; eq:LTI}; ; \dot{; ; x}; ; (t) = A x(t) + Bu(t), \ ; \ ; y(t)=Cx(t) \end{; ; equation}; ; with the system matrix $A \in \Real^{; ; n \times n}; ; $ where $n$ can be larger than $10^5$, with the input $B \in \Real^{; ; n \times m}; ; $, and the output matrix $C \in \Real^{; ; p \times n}; ; $, where $m, p\ll n$, one of the approaches is to approximate the system's transfer function \begin{; ; align}; ; \label{; ; intro:eq:TF}; ; \nice{; ; G}; ; (s) = C (sI-A)^{; ; -1}; ; B, \ ; \ ; s\in\mathbf{; ; i}; ; \Real. \end{; ; align}; ; by a more convenient rational function $\nice{; ; G}; ; _r(s)$ of order $r$ with $r\ll n$. One such method is the Iterative Rational Krylov Algorithm (IRKA, S. Gugercin, A.C. Antoulas, and C.A. Beattie., SIMAX 2008), which finds an approximation $\nice{; ; G}; ; _r(s)$ that is locally optimal in the norm of the Hardy space $\mathcal{; ; H}; ; _2$. At each iteration, $2r$ shifted linear systems have to be solved in order to obtain the search and the test spaces. Moreover, since IRKA finds only a locally optimal approximation, and in the process of finding an appropriate reduced order model, a user may repeat the computation with different initial shifts (hoping to find better local minimum of the approximation error), and perhaps with several values of $r$. This design process may, altogether, require solutions of several thousands shifted linear systems. Even the simple task of graphing the frequency response (Bode plot), i.e. the values of the transfer function $\nice{; ; G}; ; (s)$ requires evaluations of $(A - \sigma_j I)^{; ; -1}; ; B$ for many values $\sigma_j = \mathbf{; ; i}; ; \omega_j$, $\omega_j\in\Real$. Already for moderately large $n, m, p$, this mere function evaluation may take annoyingly long time. Regardless of hardware capabilities, the problems of middle size are still in focus. In some applications the matrix $A$ is not sparse, and its dimension $n$ is not extremely large, say $n$ is in tens of thousands at most. In such situation, the total number of shifted systems to be solved, the required accuracy of the solution, and the computing platform (e.g. massively parallel hardware, available optimized libraries) may motivate development of direct methods. In our earlier work, we used \emph{; ; controller Hessenberg form}; ; for efficient solution of a large number of shifted linear systems. The reduction to this form exploits parallel environment very successfully, providing a convenient starting point for the linear solver in the second phase, by reducing number of operations and memory traffic. Shifted linear systems for different shifts are further solved simultaneously. Since modern computers offer execution of numerical algorithms in parallel, performing operations on both CPU and GPU, we adapted this approach to a hybrid CPU+GPU setting. The controller Hessenberg form is computed by splitting the workload between the CPU and the GPU, while the second phase is done entirely on the massively parallel GPU. Besides the efficient BLAS3 operations, we make further use of independent operations that can be carried out simultaneously for different shifts. We will present our IRKA implementation which is to our best knowledge the first one based of parallel solvers, making it highly parallelizable and efficient.