Search

This article is devoted to the polynomial eigenvalue decomposition (PEVD) and its applications in broadband multichannel signal processing, motivated by the optimum solutions provided by the eigenvalue decomposition (EVD) for the narrow-band case [1], [2]. In general, the successful techniques from narrowband problems can also be applied to broadband ones, leading to improved solutions. Multichannel broadband signals arise at the core of many essential commercial applications such as telecommunications, speech processing, healthcare monitoring, astronomy and seismic surveillance, and military technologies like radar, sonar and communications [3]. The success of these applications often depends on the performance of signal processing tasks, including data compression [4], source localization [5], channel coding [6], signal enhancement [7], beamforming [8], and source separation [9]. In most cases and for narrowband signals, performing an EVD is the key to the signal processing algorithm. Therefore, this paper aims to introduce PEVD as a novel mathematical technique suitable for many broadband signal processing applications.

In this work we study the convergence properties of the one-level parallel Schwarz method with Robin transmission conditions applied to the one-dimensional and two-dimensional Helmholtz and Maxwell's equations. One-level methods are not scalable in general. However, it has recently been proven that when impedance transmission conditions are used in the case of the algorithm being applied to the equations with absorption, then, under certain assumptions, scalability can be achieved and no coarse space is required. We show here that this result is also true for the iterative version of the method at the continuous level for strip-wise decompositions into subdomains that are typically encountered when solving wave-guide problems. The convergence proof relies on the particular block Toeplitz structure of the global iteration matrix. Although non-Hermitian, we prove that its limiting spectrum has a near identical form to that of a Hermitian matrix of the same structure. We illustrate our results with numerical experiments.

A Hungarian scaling is a diagonal scaling of a matrix that is typically applied along 5 with a permutation to a sparse linear system before calling a direct or iterative solver. A matrix that 6 has been Hungarian scaled and reordered has all entries of modulus less than or equal to 1 and entries 7 of modulus 1 on the diagonal. An important fact that has been largely overlooked by the previous8 research into Hungarian scaling of linear systems is that a given matrix typically has a range of 9 possible Hungarian scalings and direct or iterative solvers may behave quite differently under each of 10 these scalings. Since standard algorithms for computing Hungarian scalings return only one scaling, 11 it is natural to ask whether a superior performing scaling can be obtained by searching within the 12 set of all possible Hungarian scalings. To this end we propose a method for computing a Hungarian 13 scaling that is optimal from the point of view of a measure of diagonal dominance. Our method uses 14 max-balancing, which minimizes the largest off-diagonal entries in the scaled and permuted matrix.15 Numerical experiments illustrate the increased diagonal dominance produced by max-balanced Hun-16 garian scaling as well as the reduced need for row interchanges in Gaussian elimination with partial17 pivoting and the improved stability of LU factorizations without pivoting. We additionally find that18 applying the max-balancing scaling before computing incomplete LU preconditioners improves the 19 convergence rate of certain iterative methods. Our numerical experiments also show that the Hun-20 garian scaling returned by the HSL code MC64 has performance very close to that of the optimal21 max-balanced Hungarian scaling, which further supports the use of this code in practice.

In Weiss (2018), we stated that any positive semi-definite parahermitian matrix R (z): C→CMxM that is analytic on an annulus containing at least the unit circle will admit a decomposition with analytic eigenvalues and analytic eigenvectors. In this note, we further qualify this statement, and define the class of matrices that fulfills the above properties yet does not admit an analytic EVD. We follow the notation in Weiss (2018).

This paper addresses the extension of the factorisation of a Hermitian matrix by an eigenvalue decomposition (EVD) to the case of a parahermitian matrix that is analytic at least on an annulus containing the unit circle. Such parahermitian matrices contain polynomials or rational functions in the complex variable z, and arise e.g. as cross spectral density matrices in broadband array problems. Specifically, conditions for the existence and uniqueness of eigenvalues and eigenvectors of a parahermitian matrix EVD are given, such that these can be represented by a power or Laurent series that is absolutely convergent, at least on the unit circle, permitting a direct realisation in the time domain. Based on an analysis on the unit circle, we prove that eigenvalues exist as unique and convergent but likely infinite-length Laurent series. The eigenvectors can have an arbitrary phase response, and are shown to exist as convergent Laurent series if eigenvalues are selected as analytic functions on the unit circle, and if the phase response is selected such that the eigenvectors are Hölder continuous with α>½ on the unit circle. In the case of a discontinuous phase response or if spectral majorisation is enforced for intersecting eigenvalues, an absolutely convergent Laurent series solution for the eigenvectors of a parahermitian EVD does not exist. We provide some examples, comment on the approximation of a parahermitian matrix EVD by Laurent polynomial factors, and compare our findings to the solutions provided by polynomial matrix EVD algorithms.

Among optimal hierarchical algorithms for the computational solution of elliptic problems, the Fast Multipole Method (FMM) stands out for its adaptability to emerging architectures, having high arithmetic intensity, tunable accuracy, and relaxable global synchronization requirements. We demonstrate that, beyond its traditional use as a solver in problems for which explicit free-space kernel representations are available, the FMM has applicability as a preconditioner in finite domain elliptic boundary value problems, by equipping it with boundary integral capability for satisfying conditions at finite boundaries and by wrapping it in a Krylov method for extensibility to more general operators. Here, we do not discuss the well developed applications of FMM to implement matrix-vector multiplications within Krylov solvers of boundary element methods. Instead, we propose using FMM for the volume-to-volume contribution of inhomogeneous Poisson-like problems, where the boundary integral is a small part of the overall computation. Our method may be used to precondition sparse matrices arising from finite difference/element discretizations, and can handle a broader range of scientific applications. Compared with multigrid methods, it is capable of comparable algebraic convergence rates down to the truncation error of the discretized PDE, and it offers potentially superior multicore and distributed memory scalability properties on commodity architecture supercomputers. Compared with other methods exploiting the low rank character of off-diagonal blocks of the dense resolvent operator, FMM-preconditioned Krylov iteration may reduce the amount of communication because it is matrix-free and exploits the tree structure of FMM. We describe our tests in reproducible detail with freely available codes and outline directions for further extensibility., Comment: 17 pages, 9 figures

State of the art narrowband noise cancellation techniques utilise the generalised eigenvalue decomposition (GEVD) for multichannel Wiener filtering which can be applied to independent frequency bins in order to achieve broadband processing. Here we investigate the extension of the GEVD to broadband, polynomial matrices, akin to strategies that have already been developed by McWhirter et. al on the polynomial matrix eigenvalue decomposition (PEVD).

Submitted by Isabel Gomes (itg@lisboa.ucp.pt) on 2016-09-08T10:33:33Z No. of bitstreams: 2 Dissertation_1502114079.pdf: 13673101 bytes, checksum: 18ef437e797b4a7055c1fece3c7a9ff0 (MD5) Cover Page and Abstract_1502114079.pdf: 174683 bytes, checksum: 2d45c2359e2ee9e18918c2c58a942e98 (MD5) Approved for entry into archive by Isabel Gomes (itg@lisboa.ucp.pt) on 2016-09-08T10:33:49Z (GMT) No. of bitstreams: 2 Dissertation_1502114079.pdf: 13673101 bytes, checksum: 18ef437e797b4a7055c1fece3c7a9ff0 (MD5) Cover Page and Abstract_1502114079.pdf: 174683 bytes, checksum: 2d45c2359e2ee9e18918c2c58a942e98 (MD5) Made available in DSpace on 2016-09-08T10:33:49Z (GMT). No. of bitstreams: 2 Dissertation_1502114079.pdf: 13673101 bytes, checksum: 18ef437e797b4a7055c1fece3c7a9ff0 (MD5) Cover Page and Abstract_1502114079.pdf: 174683 bytes, checksum: 2d45c2359e2ee9e18918c2c58a942e98 (MD5) Previous issue date: 2016-06-06