Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • 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
On solving symmetric systems of linear equations in an unnormalized Krylov subspace framework
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.ORCID iD: 0000-0002-6252-7815
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
(English)Article in journal (Other academic) Submitted
Abstract [en]

In an unnormalized Krylov subspace framework for solving symmetric systems of linear equations, the orthogonal vectors that are generated by a Lanczos process are not necessarily on the form of gradients. Associating each orthogonal vector with a triple, and using only the three-term recurrences of the triples, we give conditions on whether a symmetric system of linear equations is compatible or incompatible. In the compatible case, a solution is given and in the incompatible case, a certificate of incompatibility is obtained. In particular, the case when the matrix is singular is handled.

We also derive a minimum-residual method based on this framework and show how the iterates may be updated explicitly based on the triples, and in the incompatible case a minimum-residual solution of minimum Euclidean norm is obtained.

Keyword [en]
Krylov subspace method, symmetric system of linear equations, unnormalized Lanczos vectors, minimum-residual method
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-166671OAI: oai:DiVA.org:kth-166671DiVA: diva2:811786
Funder
Swedish Research Council
Note

QS 2015

Available from: 2015-05-13 Created: 2015-05-13 Last updated: 2015-05-19Bibliographically approved
In thesis
1. On Methods for Solving Symmetric Systems of Linear Equations Arising in Optimization
Open this publication in new window or tab >>On Methods for Solving Symmetric Systems of Linear Equations Arising in Optimization
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis we present research on mathematical properties of methods for solv- ing symmetric systems of linear equations that arise in various optimization problem formulations and in methods for solving such problems.

In the first and third paper (Paper A and Paper C), we consider the connection be- tween the method of conjugate gradients and quasi-Newton methods on strictly convex quadratic optimization problems or equivalently on a symmetric system of linear equa- tions with a positive definite matrix. We state conditions on the quasi-Newton matrix and the update matrix such that the search directions generated by the corresponding quasi-Newton method and the method of conjugate gradients respectively are parallel.

In paper A, we derive such conditions on the update matrix based on a sufficient condition to obtain mutually conjugate search directions. These conditions are shown to be equivalent to the one-parameter Broyden family. Further, we derive a one-to-one correspondence between the Broyden parameter and the scaling between the search directions from the method of conjugate gradients and a quasi-Newton method em- ploying some well-defined update scheme in the one-parameter Broyden family.

In paper C, we give necessary and sufficient conditions on the quasi-Newton ma- trix and on the update matrix such that equivalence with the method of conjugate gra- dients hold for the corresponding quasi-Newton method. We show that the set of quasi- Newton schemes admitted by these necessary and sufficient conditions is strictly larger than the one-parameter Broyden family. In addition, we show that this set of quasi- Newton schemes includes an infinite number of symmetric rank-one update schemes.

In the second paper (Paper B), we utilize an unnormalized Krylov subspace frame- work for solving symmetric systems of linear equations. These systems may be incom- patible and the matrix may be indefinite/singular. Such systems of symmetric linear equations arise in constrained optimization. In the case of an incompatible symmetric system of linear equations we give a certificate of incompatibility based on a projection on the null space of the symmetric matrix and characterize a minimum-residual solu- tion. Further we derive a minimum-residual method, give explicit recursions for the minimum-residual iterates and characterize a minimum-residual solution of minimum Euclidean norm.

Abstract [sv]

I denna avhandling betraktar vi matematiska egenskaper hos metoder för att lösa symmetriska linjära ekvationssystem som uppkommer i formuleringar och metoder för en mängd olika optimeringsproblem.

I första och tredje artikeln (Paper A och Paper C), undersöks kopplingen mellan konjugerade gradientmetoden och kvasi-Newtonmetoder när dessa appliceras på strikt konvexa kvadratiska optimeringsproblem utan bivillkor eller ekvivalent på ett symmet- risk linjärt ekvationssystem med en positivt definit symmetrisk matris. Vi ställer upp villkor på kvasi-Newtonmatrisen och uppdateringsmatrisen så att sökriktningen som fås från motsvarande kvasi-Newtonmetod blir parallell med den sökriktning som fås från konjugerade gradientmetoden.

I den första artikeln (Paper A), härleds villkor på uppdateringsmatrisen baserade på ett tillräckligt villkor för att få ömsesidigt konjugerade sökriktningar. Dessa villkor på kvasi-Newtonmetoden visas vara ekvivalenta med att uppdateringsstrategin tillhör Broydens enparameterfamilj. Vi tar också fram en ett-till-ett överensstämmelse mellan Broydenparametern och skalningen mellan sökriktningarna från konjugerade gradient- metoden och en kvasi-Newtonmetod som använder någon väldefinierad uppdaterings- strategi från Broydens enparameterfamilj.

I den tredje artikeln (Paper C), ger vi tillräckliga och nödvändiga villkor på en kvasi-Newtonmetod så att nämnda ekvivalens med konjugerade gradientmetoden er- hålls. Mängden kvasi-Newtonstrategier som uppfyller dessa villkor är strikt större än Broydens enparameterfamilj. Vi visar också att denna mängd kvasi-Newtonstrategier innehåller ett oändligt antal uppdateringsstrategier där uppdateringsmatrisen är en sym- metrisk matris av rang ett.

I den andra artikeln (Paper B), används ett ramverk för icke-normaliserade Krylov- underrumsmetoder för att lösa symmetriska linjära ekvationssystem. Dessa ekvations- system kan sakna lösning och matrisen kan vara indefinit/singulär. Denna typ av sym- metriska linjära ekvationssystem uppkommer i en mängd formuleringar och metoder för optimeringsproblem med bivillkor. I fallet då det symmetriska linjära ekvations- systemet saknar lösning ger vi ett certifikat för detta baserat på en projektion på noll- rummet för den symmetriska matrisen och karaktäriserar en minimum-residuallösning. Vi härleder även en minimum-residualmetod i detta ramverk samt ger explicita rekur- sionsformler för denna metod. I fallet då det symmetriska linjära ekvationssystemet saknar lösning så karaktäriserar vi en minimum-residuallösning av minsta euklidiska norm.

Place, publisher, year, edition, pages
KTH Royal Institute of Technology, 2015. xii, 18 p.
Series
TRITA-MAT-A, 2015:05
Keyword
symmetric system of linear equations, method of conjugate gradients, quasi-Newton method, unconstrained optimization, unconstrained quadratic optimiza- tion, Krylov subspace method, unnormalized Lanczos vectors, minimum-residual method, symmetriska linjära ekvationssystem, konjugerade gradientmetoden, kvasi- Newtonmetoder, optimering utan bivillkor, kvadratisk optimering utan bivillkor, Kry- lovunderrumsmetoder, icke-normaliserade Lanczosvektorer, minimum-residualmetoden
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-166675 (URN)978-91-7595-514-8 (ISBN)
Public defence
2015-06-12, F3, Lindstedtsvägen 26, KTH, Stockholm, 14:00 (English)
Opponent
Supervisors
Funder
Swedish Research Council
Note

QC 20150519

Available from: 2015-05-19 Created: 2015-05-13 Last updated: 2015-05-22Bibliographically approved

Open Access in DiVA

No full text

Other links

arXiv

Authority records BETA

Forsgren, Anders

Search in DiVA

By author/editor
Forsgren, AndersOdland, Tove
By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 57 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • 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