uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Matrix-Less Methods for Computing Eigenvalues of Large Structured Matrices
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Numerical Analysis.ORCID iD: 0000-0002-7875-7543
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

When modeling natural phenomena with linear partial differential equations, the discretized system of equations is in general represented by a matrix. To solve or analyze these systems, we are often interested in the spectral behavior of these matrices. Whenever the matrices of interest are Toeplitz, or Toeplitz-like, we can use the theory of Generalized Locally Toeplitz (GLT) sequences to study the spectrum (eigenvalues). A central concept in the theory of GLT sequences is the so-called symbol, that is, a function associated with a sequence of matrices of increasing size. When sampling the symbol and when the related matrix sequence is Hermitian (or quasi-Hermitian), we obtain an approximation of the spectrum of a matrix of a fixed size and we can therefore see its general behavior. However, the so-computed approximations of the eigenvalues are often affected by errors having magnitude of the reciprocal of the matrix size.

In this thesis we develop novel methods, which we call "matrix-less" since they neither store the matrices of interest nor depend on matrix-vector products, to estimate these errors. Moreover, we exploit the structures of the considered matrices to efficiently and accurately compute the spectrum.

We begin by considering the errors of the approximate eigenvalues computed by sampling the symbol on a uniform grid, and we conjecture the existence of an asymptotic expansion for these errors. We devise an algorithm to approximate the expansion by using a small number of moderately sized matrices, and we show through numerical experiments the effectiveness of the algorithm. We also show that the same algorithm works for preconditioned matrices, a result which is important in practical applications. Then, we explain how to use the approximated expansion on the whole spectrum for large matrices, whereas in earlier works its applicability was restricted only to certain matrix sizes and to a subset of the spectrum. Next, we demonstrate how to use the so-developed techniques to investigate, solve, and improve the accuracy in the eigenvalue computations for various differential problems discretized by the isogeometric analysis (IgA) method. Lastly, we discuss a class of non-monotone symbols for which we construct the sampling grid yielding exact eigenvalues and eigenvectors.

To summarize, we show, both theoretically and numerically, the applicability of the presented matrix-less methods for a wide variety of problems.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2018. , p. 81
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1652
Keywords [en]
Toeplitz matrices, eigenvalues, eigenvalue asymptotics, polynomial interpolation, extrapolation, generating function and spectral symbol
National Category
Computational Mathematics
Research subject
Scientific Computing with specialization in Numerical Analysis
Identifiers
URN: urn:nbn:se:uu:diva-346735ISBN: 978-91-513-0288-1 (print)OAI: oai:DiVA.org:uu-346735DiVA, id: diva2:1192980
Public defence
2018-05-18, 2446 ITC, Lägerhyddsvägen 2, hus 2, Uppsala, 10:15 (English)
Opponent
Supervisors
Available from: 2018-04-20 Created: 2018-03-25 Last updated: 2018-10-08
List of papers
1. Are the eigenvalues of banded symmetric Toeplitz matrices known in almost closed form?
Open this publication in new window or tab >>Are the eigenvalues of banded symmetric Toeplitz matrices known in almost closed form?
2018 (English)In: Experimental Mathematics, ISSN 1058-6458, E-ISSN 1944-950X, Vol. 27, p. 478-487Article in journal (Refereed) Published
National Category
Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-322240 (URN)10.1080/10586458.2017.1320241 (DOI)000455366200011 ()
Available from: 2017-05-16 Created: 2017-05-17 Last updated: 2019-02-14Bibliographically approved
2. Are the eigenvalues of preconditioned banded symmetric Toeplitz matrices known in almost closed form?
Open this publication in new window or tab >>Are the eigenvalues of preconditioned banded symmetric Toeplitz matrices known in almost closed form?
Show others...
2018 (English)In: Numerical Algorithms, ISSN 1017-1398, E-ISSN 1572-9265, Vol. 78, p. 867-893Article in journal (Refereed) Published
National Category
Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-328780 (URN)10.1007/s11075-017-0404-z (DOI)000435692900010 ()
Available from: 2017-08-31 Created: 2017-08-31 Last updated: 2019-01-22Bibliographically approved
3. A matrix-less and parallel interpolation–extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric Toeplitz matrices
Open this publication in new window or tab >>A matrix-less and parallel interpolation–extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric Toeplitz matrices
2019 (English)In: Numerical Algorithms, ISSN 1017-1398, E-ISSN 1572-9265, Vol. 80, p. 819-848Article in journal (Refereed) Published
National Category
Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-346734 (URN)10.1007/s11075-018-0508-0 (DOI)000461382900007 ()
Available from: 2018-03-24 Created: 2018-03-21 Last updated: 2019-05-02Bibliographically approved
4. Are the eigenvalues of the B-spline IgA approximation of −Δuλu known in almost closed form?
Open this publication in new window or tab >>Are the eigenvalues of the B-spline IgA approximation of −Δuλu known in almost closed form?
2017 (English)Report (Other academic)
Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2017-016
National Category
Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-328783 (URN)
Available from: 2017-08-31 Created: 2017-08-31 Last updated: 2019-01-22Bibliographically approved
5. Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols
Open this publication in new window or tab >>Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols
2018 (English)In: Numerical Linear Algebra with Applications, ISSN 1070-5325, E-ISSN 1099-1506, Vol. 25, p. e2137:1-17, article id e2137Article in journal (Refereed) Published
National Category
Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-340511 (URN)10.1002/nla.2137 (DOI)000448861300001 ()
Available from: 2018-01-29 Created: 2018-01-31 Last updated: 2019-01-24Bibliographically approved

Open Access in DiVA

fulltext(2943 kB)110 downloads
File information
File name FULLTEXT01.pdfFile size 2943 kBChecksum SHA-512
ffb82e6a9ce79e01e41854a9e40df2f6c45e89af044c34a69354f15559602d5db310d816c922a1553abd7c682351479b26eb213d33d3bc06e07c44a233a776a0
Type fulltextMimetype application/pdf
errata(25 kB)20 downloads
File information
File name ERRATA01.pdfFile size 25 kBChecksum SHA-512
70737466b190798cb417a798cc94dfaf7127690d5d2103ba1290a0b7f818a209182a4872eaf4c7f48e5ec75e991882011c48f676dc7bf24c6d3088314b5d48b7
Type errataMimetype application/pdf
Buy this publication >>

Search in DiVA

By author/editor
Ekström, Sven-Erik
By organisation
Division of Scientific ComputingNumerical Analysis
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 110 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1208 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf