# Solution of Large Linear Systems of Equations by Conjugate Gradient Type Methods

Ontology type: schema:Chapter

### Chapter Info

DATE

1983

AUTHORS ABSTRACT

In 1952, Hestenes and Stiefel introduced the conjugate gradient algorithm in their landmark paper [27] as an algorithm for solving linear equation Ax = b with A as positive definite n × n-matrix (see the book [26] of Hestenes for a broad exposition). The algorithm fascinated numerical analysts since then for various reasons: The cg-algorithm combines features of direct and iterative methods which attracted the attention in the early years: It generates a sequence xi of vectors approximating the solution \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\overline x$$\end{document} in a defined way like other iterative methods, but like direct methods, terminating with the exact solution after at most n steps, at least in theory. Many expectations were disappointed, when it was found out that due to roundoff the n-step termination property does not hold in practice. However, viewed as an iterative method, the cg-algorithm has very attractive features. Its application for the iterative solution of large sparse systems has been discussed very early [11] by Stiefel and his coworkers. Like other iterative methods, it essentially requires only the formation of one matrix-vector product A·x per iteration, so that the iterations are inexpensive even for large matrices A, if they are sparse. The iterative aspect of the method has been particularly emphasized since the work of Reid [38]. More... »

PAGES

540-565

### Book

TITLE

Mathematical Programming The State of the Art

ISBN

978-3-642-68876-8
978-3-642-68874-4

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-68874-4_21

DOI

http://dx.doi.org/10.1007/978-3-642-68874-4_21

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1042820991

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institut f\u00fcr Angew. Mathematik, Universit\u00e4t W\u00fcrzburg, Am Hubland, 8700, W\u00fcrzburg, Germany",
"id": "http://www.grid.ac/institutes/grid.8379.5",
"name": [
"Institut f\u00fcr Angew. Mathematik, Universit\u00e4t W\u00fcrzburg, Am Hubland, 8700, W\u00fcrzburg, Germany"
],
"type": "Organization"
},
"familyName": "Stoer",
"givenName": "J.",
"id": "sg:person.011465456275.61",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011465456275.61"
],
"type": "Person"
}
],
"datePublished": "1983",
"datePublishedReg": "1983-01-01",
"description": "In 1952, Hestenes and Stiefel introduced the conjugate gradient algorithm in their landmark paper [27] as an algorithm for solving linear equation Ax = b with A as positive definite n \u00d7 n-matrix (see the book [26] of Hestenes for a broad exposition). The algorithm fascinated numerical analysts since then for various reasons: The cg-algorithm combines features of direct and iterative methods which attracted the attention in the early years: It generates a sequence xi of vectors approximating the solution \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\overline x$$\\end{document} in a defined way like other iterative methods, but like direct methods, terminating with the exact solution after at most n steps, at least in theory. Many expectations were disappointed, when it was found out that due to roundoff the n-step termination property does not hold in practice. However, viewed as an iterative method, the cg-algorithm has very attractive features. Its application for the iterative solution of large sparse systems has been discussed very early [11] by Stiefel and his coworkers. Like other iterative methods, it essentially requires only the formation of one matrix-vector product A\u00b7x per iteration, so that the iterations are inexpensive even for large matrices A, if they are sparse. The iterative aspect of the method has been particularly emphasized since the work of Reid [38].",
"editor": [
{
"familyName": "Bachem",
"givenName": "Achim",
"type": "Person"
},
{
"familyName": "Korte",
"givenName": "Bernhard",
"type": "Person"
},
{
"familyName": "Gr\u00f6tschel",
"givenName": "Martin",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-68874-4_21",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-68876-8",
"978-3-642-68874-4"
],
"name": "Mathematical Programming The State of the Art",
"type": "Book"
},
"keywords": [
"iterative method",
"linear equations Ax",
"large sparse systems",
"large linear systems",
"matrix-vector products",
"work of Reid",
"equations Ax",
"linear systems",
"sparse systems",
"numerical analysts",
"exact solution",
"iterative solution",
"type method",
"large matrices",
"Stiefel",
"direct method",
"termination properties",
"iteration",
"algorithm",
"attractive features",
"solution",
"Hestenes",
"roundoff",
"equations",
"matrix",
"landmark paper",
"theory",
"system",
"vector",
"iterative aspect",
"axes",
"properties",
"applications",
"XI",
"features",
"work",
"step",
"Reid",
"coworkers",
"way",
"analysts",
"aspects",
"expectations",
"attention",
"reasons",
"formation",
"products",
"practice",
"early years",
"years",
"method",
"paper"
],
"name": "Solution of Large Linear Systems of Equations by Conjugate Gradient Type Methods",
"pagination": "540-565",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1042820991"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-68874-4_21"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-68874-4_21",
"https://app.dimensions.ai/details/publication/pub.1042820991"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-06-01T22:33",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_376.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-68874-4_21"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-68874-4_21'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-68874-4_21'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-68874-4_21'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-68874-4_21'

This table displays all metadata directly associated to this object as RDF triples.

126 TRIPLES      23 PREDICATES      82 URIs      75 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0103
3 schema:author Nbd219623a0134cd3a24419880056245f
4 schema:datePublished 1983
5 schema:datePublishedReg 1983-01-01
6 schema:description In 1952, Hestenes and Stiefel introduced the conjugate gradient algorithm in their landmark paper [27] as an algorithm for solving linear equation Ax = b with A as positive definite n × n-matrix (see the book [26] of Hestenes for a broad exposition). The algorithm fascinated numerical analysts since then for various reasons: The cg-algorithm combines features of direct and iterative methods which attracted the attention in the early years: It generates a sequence xi of vectors approximating the solution \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\overline x$$\end{document} in a defined way like other iterative methods, but like direct methods, terminating with the exact solution after at most n steps, at least in theory. Many expectations were disappointed, when it was found out that due to roundoff the n-step termination property does not hold in practice. However, viewed as an iterative method, the cg-algorithm has very attractive features. Its application for the iterative solution of large sparse systems has been discussed very early [11] by Stiefel and his coworkers. Like other iterative methods, it essentially requires only the formation of one matrix-vector product A·x per iteration, so that the iterations are inexpensive even for large matrices A, if they are sparse. The iterative aspect of the method has been particularly emphasized since the work of Reid [38].
7 schema:editor Nc3103a57ebda4d929d4af9416f1857a2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8bdb5cc27d66403587e02a3cdd2f22c3
12 schema:keywords Hestenes
13 Reid
14 Stiefel
15 XI
16 algorithm
17 analysts
18 applications
19 aspects
20 attention
21 attractive features
22 axes
25 coworkers
26 direct method
27 early years
28 equations
29 equations Ax
30 exact solution
31 expectations
32 features
33 formation
36 iteration
37 iterative aspect
38 iterative method
39 iterative solution
40 landmark paper
41 large linear systems
42 large matrices
43 large sparse systems
44 linear equations Ax
45 linear systems
46 matrix
47 matrix-vector products
48 method
49 numerical analysts
50 paper
51 practice
52 products
53 properties
54 reasons
55 roundoff
56 solution
57 sparse systems
58 step
59 system
60 termination properties
61 theory
62 type method
63 vector
64 way
65 work
66 work of Reid
67 years
68 schema:name Solution of Large Linear Systems of Equations by Conjugate Gradient Type Methods
69 schema:pagination 540-565
70 schema:productId N6d2c5e1b14fc475ca4bb62d7703ab204
71 N87807cabe20142b98b5d24dc3e9546a1
72 schema:publisher Na4f339a1e37c4e8e9a426377c7213220
73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042820991
74 https://doi.org/10.1007/978-3-642-68874-4_21
75 schema:sdDatePublished 2022-06-01T22:33
77 schema:sdPublisher Ncfb3573c581e41e6aa97803b2d71e5bb
78 schema:url https://doi.org/10.1007/978-3-642-68874-4_21
80 sgo:sdDataset chapters
81 rdf:type schema:Chapter
82 N16493065bf814074b7def519047246c8 schema:familyName Grötschel
83 schema:givenName Martin
84 rdf:type schema:Person
85 N2eb257c264cb4fc686bcdbe38321582a schema:familyName Korte
86 schema:givenName Bernhard
87 rdf:type schema:Person
88 N3fba27c428b649c2bcce0e340d0c45ae rdf:first N2eb257c264cb4fc686bcdbe38321582a
89 rdf:rest N6b8af830b50e4e04861420f5fb5a513f
90 N6b8af830b50e4e04861420f5fb5a513f rdf:first N16493065bf814074b7def519047246c8
91 rdf:rest rdf:nil
92 N6d2c5e1b14fc475ca4bb62d7703ab204 schema:name doi
93 schema:value 10.1007/978-3-642-68874-4_21
94 rdf:type schema:PropertyValue
95 N87807cabe20142b98b5d24dc3e9546a1 schema:name dimensions_id
96 schema:value pub.1042820991
97 rdf:type schema:PropertyValue
98 N8bdb5cc27d66403587e02a3cdd2f22c3 schema:isbn 978-3-642-68874-4
99 978-3-642-68876-8
100 schema:name Mathematical Programming The State of the Art
101 rdf:type schema:Book
102 Na4f339a1e37c4e8e9a426377c7213220 schema:name Springer Nature
103 rdf:type schema:Organisation
104 Naf355f758109430f88bdcd38b352b68b schema:familyName Bachem
105 schema:givenName Achim
106 rdf:type schema:Person
107 Nbd219623a0134cd3a24419880056245f rdf:first sg:person.011465456275.61
108 rdf:rest rdf:nil
109 Nc3103a57ebda4d929d4af9416f1857a2 rdf:first Naf355f758109430f88bdcd38b352b68b
110 rdf:rest N3fba27c428b649c2bcce0e340d0c45ae
111 Ncfb3573c581e41e6aa97803b2d71e5bb schema:name Springer Nature - SN SciGraph project
112 rdf:type schema:Organization
113 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
114 schema:name Mathematical Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
117 schema:name Numerical and Computational Mathematics
118 rdf:type schema:DefinedTerm
119 sg:person.011465456275.61 schema:affiliation grid-institutes:grid.8379.5
120 schema:familyName Stoer
121 schema:givenName J.
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011465456275.61
123 rdf:type schema:Person
124 grid-institutes:grid.8379.5 schema:alternateName Institut für Angew. Mathematik, Universität Würzburg, Am Hubland, 8700, Würzburg, Germany
125 schema:name Institut für Angew. Mathematik, Universität Würzburg, Am Hubland, 8700, Würzburg, Germany
126 rdf:type schema:Organization