Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA generalized eigenvalue algorithm for tridiagonal matrix pencils based on a nonautonomous discrete integrable system
142
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A generalized eigenvalue algorithm for tridiagonal matrix pencils is presented. The algorithm appears as the time evolution equation of a nonautonomous discrete integrable system associated with a polynomial sequence which has some orthogonality on the support set of the zeros of the characteristic polynomial for a tridiagonal matrix pencil. The convergence of the algorithm is discussed by using the solution to the initial value problem for the corresponding discrete integrable system.
rate research
Read More
We design a fast implicit real QZ algorithm for eigenvalue computation of structured companion pencils arising from linearizations of polynomial rootfinding problems. The modified QZ algorithm computes the generalized eigenvalues of an $Ntimes N$ structured matrix pencil using $O(N)$ flops per iteration and $O(N)$ memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.
In this paper, a parallel structured divide-and-conquer (PSDC) eigensolver is proposed for symmetric tridiagonal matrices based on ScaLAPACK and a parallel structured matrix multiplication algorithm, called PSMMA. Computing the eigenvectors via matrix-matrix multiplications is the most computationally expensive part of the divide-and-conquer algorithm, and one of the matrices involved in such multiplications is a rank-structured Cauchy-like matrix. By exploiting this particular property, PSMMA constructs the local matrices by using generators of Cauchy-like matrices without any communication, and further reduces the computation costs by using a structured low-rank approximation algorithm. Thus, both the communication and computation costs are reduced. Experimental results show that both PSMMA and PSDC are highly scalable and scale to 4096 processes at least. PSDC has better scalability than PHDC that was proposed in [J. Comput. Appl. Math. 344 (2018) 512--520] and only scaled to 300 processes for the same matrices. Comparing with texttt{PDSTEDC} in ScaLAPACK, PSDC is always faster and achieves $1.4$x--$1.6$x speedup for some matrices with few deflations. PSDC is also comparable with ELPA, with PSDC being faster than ELPA when using few processes and a little slower when using many processes.
We contribute to the algebraic-geometric study of discrete integrable systems generated by planar birational maps: (a) we find geometric description of Manin involutions for elliptic pencils consisting of curves of higher degree, birationally equivalent to cubic pencils (Halphen pencils of index 1), and (b) we characterize special geometry of base points ensuring that certain compositions of Manin involutions are integrable maps of low degree (quadratic Cremona maps). In particular, we identify some integrable Kahan discretizations as compositions of Manin involutions for elliptic pencils of higher degree.
Composite function minimization captures a wide spectrum of applications in both computer vision and machine learning. It includes bound constrained optimization, $ell_1$ norm regularized optimization, and $ell_0$ norm regularized optimization as special cases. This paper proposes and analyzes a new Generalized Matrix Splitting Algorithm (GMSA) for minimizing composite functions. It can be viewed as a generalization of the classical Gauss-Seidel method and the Successive Over-Relaxation method for solving linear systems in the literature. Our algorithm is derived from a novel triangle operator mapping, which can be computed exactly using a new generalized Gaussian elimination procedure. We establish the global convergence, convergence rate, and iteration complexity of GMSA for convex problems. In addition, we also discuss several important extensions of GMSA. Finally, we validate the performance of our proposed method on three particular applications: nonnegative matrix factorization, $ell_0$ norm regularized sparse coding, and $ell_1$ norm regularized Dantzig selector problem. Extensive experiments show that our method achieves state-of-the-art performance in term of both efficiency and efficacy.
We constructed involutions for a Halphen pencil of index 2, and proved that the birational mapping corresponding to the autonomous reduction of the elliptic Painleve equation for the same pencil can be obtained as the composition of two such involutions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
