File: Sparse-Iterative-Solvers-Types.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (122 lines) | stat: -rw-r--r-- 6,606 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".

(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library &ndash; Reference Manual: Sparse Iterative Solvers Types</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Sparse Iterative Solvers Types">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Sparse Iterative Solvers Types">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Sparse-Iterative-Solvers.html#Sparse-Iterative-Solvers" rel="up" title="Sparse Iterative Solvers">
<link href="Iterating-the-Sparse-Linear-System.html#Iterating-the-Sparse-Linear-System" rel="next" title="Iterating the Sparse Linear System">
<link href="Sparse-Iterative-Solver-Overview.html#Sparse-Iterative-Solver-Overview" rel="previous" title="Sparse Iterative Solver Overview">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Sparse-Iterative-Solvers-Types"></a>
<div class="header">
<p>
Next: <a href="Iterating-the-Sparse-Linear-System.html#Iterating-the-Sparse-Linear-System" accesskey="n" rel="next">Iterating the Sparse Linear System</a>, Previous: <a href="Sparse-Iterative-Solver-Overview.html#Sparse-Iterative-Solver-Overview" accesskey="p" rel="previous">Sparse Iterative Solver Overview</a>, Up: <a href="Sparse-Iterative-Solvers.html#Sparse-Iterative-Solvers" accesskey="u" rel="up">Sparse Iterative Solvers</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Types-of-Sparse-Iterative-Solvers"></a>
<h4 class="subsection">43.2.2 Types of Sparse Iterative Solvers</h4>

<p>The sparse linear algebra library provides the following types
of iterative solvers:
</p>
<dl>
<dt><a name="index-gsl_005fsplinalg_005fitersolve_005fgmres"></a>Sparse Iterative Type: <strong>gsl_splinalg_itersolve_gmres</strong></dt>
<dd><a name="index-gmres"></a>
<p>This specifies the Generalized Minimum Residual Method (GMRES).
This is a projection method using <em>{\cal K} = {\cal K}_m</em>
and <em>{\cal L} = A {\cal K}_m</em> where <em>{\cal K}_m</em> is
the <em>m</em>-th Krylov subspace
</p><div class="example">
<pre class="example">K_m = span( r_0, A r_0, ..., A^(m-1) r_0)
</pre></div>
<p>and <em>r_0 = b - A x_0</em> is the residual vector of the initial guess
<em>x_0</em>. If <em>m</em> is set equal to <em>n</em>, then the Krylov
subspace is <em>{\bf R}^n</em> and GMRES will provide the exact solution
<var>x</var>.  However, the goal is for the method to arrive at a very good
approximation to <var>x</var> using a much smaller subspace <em>{\cal K}_m</em>. By
default, the GMRES method selects <em>m = MIN(n,10)</em> but the user
may specify a different value for <em>m</em>. The GMRES storage
requirements grow as <em>O(n(m+1))</em> and the number of flops
grow as <em>O(4 m^2 n - 4 m^3 / 3)</em>.
</p>
<p>In the below function <code>gsl_splinalg_itersolve_iterate</code>, one
GMRES iteration is defined as projecting the approximate solution
vector onto each Krylov subspace <em>{\cal K}_1, ..., {\cal K}_m</em>,
and so <em>m</em> can be kept smaller by &quot;restarting&quot; the method
and calling <code>gsl_splinalg_itersolve_iterate</code> multiple times,
providing the updated approximation <var>x</var> to each new call. If
the method is not adequately converging, the user may try increasing
the parameter <em>m</em>.
</p>
<p>GMRES is considered a robust general purpose iterative solver, however
there are cases where the method stagnates if the matrix is not
positive-definite and fails to reduce the residual until the very last
projection onto the subspace <em>{\cal K}_n = {\bf R}^n</em>. In these
cases, preconditioning the linear system can help, but GSL does not
currently provide any preconditioners.
</p></dd></dl>

<hr>
<div class="header">
<p>
Next: <a href="Iterating-the-Sparse-Linear-System.html#Iterating-the-Sparse-Linear-System" accesskey="n" rel="next">Iterating the Sparse Linear System</a>, Previous: <a href="Sparse-Iterative-Solver-Overview.html#Sparse-Iterative-Solver-Overview" accesskey="p" rel="previous">Sparse Iterative Solver Overview</a>, Up: <a href="Sparse-Iterative-Solvers.html#Sparse-Iterative-Solvers" accesskey="u" rel="up">Sparse Iterative Solvers</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>