Nonlinearly Preconditioned Inexact Newton Algorithms.
Inexact Newton algorithms are commonly used for solving large sparse nonlinear system of equations $F(u^{\ast})=0$ arising, for example, from the discretization of partial differential equations. Even with global strategies such as linesearch or trust region, the methods often stagnate at local minima of $\|F\|$, especially for problems with unbalanced nonlinearities, because the methods do not have built-in machinery to deal with the unbalanced nonlinearities. To find the same solution $u^{\ast}$, one may want to solve instead an equivalent nonlinearly preconditioned system ${\cal F}(u^{\ast})=0$ whose nonlinearities are more balanced. In this paper, we propose and study a nonlinear additive Schwarz-based parallel nonlinear preconditioner and show numerically that the new method converges well even for some difficult problems, such as high Reynolds number flows, where a traditional inexact Newton method fails.
Introduction
. Many computational engineering problems require the numerical
solution of large sparse nonlinear system of equations, i.e., for a given nonlinear
vector u # R n , such that
starting from an initial guess u (0)
and Inexact Newton algorithms (IN) [7, 8, 11, 17] are commonly
used for solving such systems and can briefly be described here. Suppose u (k) is the
current approximate solution; a new approximate solution u (k+1) can be computed
through the following steps:
Algorithm 1.1 (IN).
1: Find the inexact Newton direction p (k) such that
Step 2: Compute the new approximate solution
Here # k is a scalar that determines how accurately the Jacobian system needs to be
solved using, for example, Krylov subspace methods [2, 3, 11, 12]. # (k) is another
scalar that determines how far one should go in the selected inexact Newton direction
[7]. IN has two well-known features, namely, (a) if the initial guess is close enough
to the desired solution then the convergence is very fast, and (b) such a good initial
# Department of Computer Science, University of Colorado, Boulder, CO 80309-0430
(cai@cs.colorado.edu). The work was supported in part by the NSF grants ASC-9457534, ECS-
and ACI-0072089, and by Lawrence Livermore National Laboratory under subcontract
B509471.
Department of Mathematics & Statistics, Old Dominion University, Norfolk, VA 23529-0077;
ISCR, Lawrence Livermore National Laboratory, Livermore, CA 94551-9989; and ICASE, NASA
Langley Research Center, Hampton, VA 23681-2199 (keyes@icase.edu). This work was supported in
part by NASA under contract NAS1-19480 and by Lawrence Livermore National Laboratory under
subcontract B347882.
guess is generally very di#cult to obtain, especially for nonlinear equations that have
unbalanced nonlinearities [19]. The step length # (k) is often determined by the components
with the worst nonlinearities, and this may lead to an extended period of
stagnation in the nonlinear residual curve; see Fig 5.2 for a typical picture and more
in the references [4, 14, 16, 23, 27, 28].
In this paper, we develop some nonlinearly preconditioned inexact Newton algorithms
Find the solution u # R n of (1.1) by solving a preconditioned system
Here the preconditioner G : R n
1. If
2. G # F -1 in some sense.
3. G(F (w)) is easily computable for w # R n .
4. If a Newton-Krylov type method is used for solving (1.4), then the matrix-vector
product (G(F (w))) # v should also be easily computable for
As in the linear equation case [13], the definition of a preconditioner can not be given
precisely, nor is it necessary. Also as in the linear equation case, preconditioning can
greatly improve the robustness of the iterative methods, since the preconditioner is
designed so that the new system (1.4) has more uniform nonlinearities. PIN takes the
following
Algorithm 1.2 (PIN).
1: Find the inexact Newton direction p (k) such that
Step 2: Compute the new approximate solution
Note that the Jacobian of the preconditioned function can be computed, at least in
theory, using the chain rule, i.e.,
#F
If G is close to F -1 in the sense that G(F (u)) # u, then #G
#F
I .
In this case, Algorithm 1.2 converges in one iteration, or few iterations, depending on
how close is G to F -1 . In fact, the same thing happens as long as G(F (u)) # Au,
where A is constant matrix independent of u. On the other hand, if G is a linear
function, then #G
would be a constant matrix independent of u. In this case the
Newton equation of the preconditioned system
reduces to the Newton equation of the original system
and G does not a#ect the nonlinear convergence of the method, except for the stopping
conditions. However, G does change the conditioning of the linear Jacobian system,
and this forms the basis for the matrix-free Newton-Krylov methods.
Most of the current research has been on the case of linear G; see, for example,
[4, 24]. In this paper, we shall focus on the case when G is the single-level nonlinear
additive Schwarz method. As an example, we show the nonlinear iteration history, in

Figure

5.2, for solving a two-dimensional flow problem with various Reynolds numbers
using the standard IN (top) and PIN (bottom). It can be seen clearly that PIN is
much less sensitive to the change of the Reynolds number than IN. Details of the
numerical experiment will be given later in the paper. Nonlinear Schwarz algorithms
have been studied extensively as iterative methods [5, 9, 20, 21, 22, 25, 26], and are
known, at least experimentally, to be not very robust, in general, unless the problem is
monotone. However, we show in the paper that nonlinear Schwarz can be an excellent
nonlinear preconditioner.
We remark that nonlinear methods can also be used as linear preconditioners as
described in [6], but we will not look into this issue in this paper.
Nested linear and nonlinear solvers are often needed in the implementation of
PIN, and as a consequence, the software is much harder to develop than for the
regular IN. Our target applications are these problems that are di#cult to solve using
traditional Newton type methods. Those include (1) problems whose solutions have
local singularities such as shocks or nonsmooth fronts; and (2) multi-physics problems
with drastically di#erent sti#ness that require di#erent nonlinear solvers based on a
single physics submodel, such as coupled fluid-structure interaction problems.
The rest of the paper is organized as follows. In section 2, we introduce the
nonlinear additive Schwarz preconditioned system and prove that under certain assumptions
it is equivalent to the original unpreconditioned system. In section 3, we
derive a formula for the Jacobian of the nonlinearly preconditioned system. The details
of the full algorithm is presented in section 4, together with some comments
about every step of the algorithm. Numerical experiments are given in section 5. In
section 6, we make some further comments and discuss some future research topics
along the line of nonlinear preconditioning. Several concluding remarks are given in
section 7.
2. A nonlinear additive Schwarz preconditioner. In this section, we describe
a nonlinear preconditioner based on the additive Schwarz method [5, 9]. Let
be an index set; i.e., one integer for each unknown u i and F i . We assume that
is a partition of S in the sense that
Here we allow the subsets to have overlap. Let n i be the dimension of S i ; then, in
general,
Using the partition of S, we introduce subspaces of R n and the corresponding restriction
and extension matrices. For each S i we define V i # R n as
and a n-n restriction (also extension) matrix I S i
whose kth column is either the kth
column of the n - n identity matrix I n-n if k # S i or zero if k # S i . Similarly, let
s be a subset of S; we denote by I s the restriction on s. Note that the matrix I s is
always symmetric and the same matrix can be used as both restriction and extension
operator. Many other forms of restriction/extension are available in the literature;
however, we only consider the simplest form in this paper.
Using the restriction operator, we define the subdomain nonlinear function as
F.
We next define the major component of the algorithm, namely the nonlinearly preconditioned
function. For any given v # R n , define T as the solution of the
following subspace nonlinear system
We introduce a new function
which we will refer to as the nonlinearly preconditioned F (u). The main contribution
of this paper is the following algorithm.
Algorithm 2.1. Find the solution u # of (1.1) by solving the nonlinearly preconditioned
system
with u (0) as the initial guess.
Remark 2.1. In the linear case, this algorithm is the same as the additive
Schwarz algorithm. Using the usual notation, if
then
where A
is the subspace inverse of A
in V i .
Remark 2.2. The evaluation of the function F(v), for a given v, involves the
calculation of the T i , which in turn involves the solution of nonlinear systems on S i .
Remark 2.3. If the overlap is zero, then this is simply a block nonlinear Jacobi
preconditioner.
Remark 2.4. If (2.2) is solved with Picard iteration, or Richardson's method,
then the algorithm is simply the nonlinear additive Schwarz method, which is not a
robust algorithm, as is known from experience with linear and nonlinear problems.
Assumption 2.1 (local unique solvability). For any s # S, we assume that
is uniquely solvable on s.
Remark 2.5. The assumption means that, for a given subset s, if both u and
are solutions on s, i.e.,
and
then if u| This assumption maybe a little too strong. A
weaker assumption could be for s to be the subsets in the partition. In this case, the
proof of the following theorem needs to be modified.
Theorem 2.1. Under the local unique solvability assumption, the nonlinear systems
and (2.2) are equivalent in the sense that they have the same solution.
Proof. Let us first assume that u # is the solution of (1.1), i.e., F
immediately implies that
By definition, T i satisfies
Comparing (2.3) and (2.4), and using the local unique solvability assumption, we must
have
Therefore, u # is a solution of (2.2).
Next, we assume that u # is a solution of (2.2) which means that
We prove that T i in two steps. First we show that T i
equals zero in the nonoverlapping part of S, then we show that T i must equal
each other in the overlapping part of S.
be the nonoverlapping part of S, i.e.,
there exists one and only one i such that k # S i },
Obviously
for any 1 # j # N . Taking ASSUMPTION 2.1, we have
for any 1 # j # N . Due to the uniqueness, we must have
for any 1 # i, j # N . Since the sum of T i (u # )| s is zero, and they all equal to each
other, they must all be zero. Thus,
. This is equivalent to saying that u # is a solution of (1.1).
3. Basic properties of the Jacobian. If (2.2) is solved using a Newton type
algorithm, then the Jacobian is needed in one form or another. We here provide a
computable form of it, and discuss some of its basic properties. Let J be the Jacobian
of the original nonlinear system, i.e.,
and JS i
, the Jacobian of the subdomain nonlinear system, i.e.,
N. Note that if F (-) is sparse nonlinear function, then J is a sparse
matrix and so are the JS i
. Unfortunately, the same thing cannot be said about the
preconditioned function F(-). Its Jacobian, generally speaking, is a dense matrix,
and is very expensive to compute and store as one may imagine. In the following
discussion, we denote by
and JS i
the Jacobian of the preconditioned whole system, and the subsystems, respectively.
Because of the definition of T i , JS i
is a n-n matrix.
components in S i , n independent variables u 1 , . , un , and its other n-n i components
are zeros.
Suppose we want to compute the Jacobian J at a given point u # R n . Consider
one subdomain S i . Let S c
be the complement of S i in S, we can write
which is correct up to an re-ordering of the independent variables
u and uS c
u. Using the definition of T i (u), we have that
Taking the derivative of the above function with respect to uS i
, we obtain
# I S i -
which implies that
assuming the subsystem Jacobian matrix #FS i
is nonsingular in the subspace V i . Next,
we take the derivative of (3.1) with respect to uS c
which is equivalent to
Note that
since the sets S i and S c
do not overlap each other. Combining (3.2) and (3.3), we
obtain
J.
Summing up (3.6) for all subdomains, we have a formula for the Jacobian of the
preconditioned nonlinear system in the form of
J.
(3.7) is an extremely interesting formula since it corresponds exactly to the additive
Schwarz preconditioned linear Jacobian system of the original un-preconditioned
equation. This fact implies that, first of all, we know how to solve the Jacobian system
of the preconditioned nonlinear system, and second, the Jacobian itself is already
well-conditioned. In other words, nonlinear preconditioning automatically o#ers a
linear preconditioning for the corresponding Jacobian system.
4. Additive Schwarz preconditioned inexact Newton algorithm. We describe
a nonlinear additive Schwarz preconditioned inexact Newton algorithm (AS-
PIN). Suppose u (0) is a given initial guess, and u (k) is the current approximate so-
lution; a new approximate solution u (k+1) can be computed through the following
steps:
Algorithm 4.1 (ASPIN).
1: Compute the nonlinear residual g through the following
two steps:
a) Find g (k)
by solving the local subdomain
nonlinear systems
with a starting point g (k)
b) Form the global residual
c) Check stopping conditions on g (k) .
Step 2: Form elements of the Jacobian of the preconditioned system
Step 3: Find the inexact Newton direction p (k) by solving the Jacobian system
approximately
Step 4: Compute the new approximate solution
where # (k) is a damping parameter.
ASPIN may look a bit complicated, but as a matter of fact, the required user
input is the same as that for the regular IN Algorithm 1.1, i.e., the user needs to
supply only two routines for each subdomain:
(1) the evaluation of the original function FS i
(w). This is needed in both Step 1
a) and Step 2 if the Jacobian is to be computed using finite-di#erence methods. It is
also needed in Step 4 in the line search steps.
(2) the Jacobian of the original function JS i
in terms of a matrix-vector multipli-
cation. This is needed in both Step 1 a) and Step 3.
We now briefly discuss the basic steps of the algorithm. In Step 1 a) of Algorithm
4.1, N subdomain nonlinear systems have to be solved in order to evaluate the
preconditioned function F at a given point. More explicitly, we solve
which has n i equations and n i unknowns, using Algorithm 1.1 with a starting value
. Note that the vector u (k)
is needed to evaluate GS i
(#), for
this requires the ghost points in a mesh-based software implementation.
In a parallel implementation, the ghost values often belong to several neighboring
processors and communication is required to obtain their current values. We note,
however, that the ghost values do not change during the solution of the subdomain
nonlinear system.
In Step 2, pieces of the Jacobian matrix are computed. The full Jacobian matrix
J never needs to be formed. In a distributed memory parallel implementation, the
submatrices JS i
are formed, and saved. The multiplication of J with a given vector is
carried out using the submatrices JS i
. Therefore the global J matrix is never needed.
Several techniques are available for computing the JS i
, for example, using an analytic
multi-colored finite di#erencing, or automatic di#erentiation. A triangular
factorization of JS i
is also performed at this step and the resulting matrices are stored.
In Step 3, the matrix
should not considered as a linear preconditioner since it does not appear on the right-hand
side of the linear system. However, using the additive Schwarz preconditioning
theory, we know that for many applications the matrix
J is well-conditioned,
under certain conditions. We also note that if an inexact solver is used to compute
w in Step 3, the Newton search direction would be changed and, as a result,
the algorithm becomes an inexact Newton algorithm.
As noted above the Jacobian system, in Step 3, does not have the standard form
of a preconditioned sparse linear system
However, standard linear solver software packages can still be used with some slight
modification, such as removing the line that performs
Since the explicit sparse format of
J is often not available, further preconditioning
of the Jacobian system using some of the sparse matrix based techniques,
such as ILU, is di#cult.
A particular interesting case is when the overlap is zero; then the diagonal blocks
of
J are all identities, therefore, do not involve any computations when
multiplied with vectors. Let us take a two-subdomain case for example,
and JS i
22 J 21 I
# .
The same thing can also be done for the overlapping case. This is a small saving when
there many small subspaces. However, the saving can be big if there are relatively few
subspaces, but the sizes are large. For example, in the case of a coupled fluid-structure
interaction simulation, there could be only two subdomains; one for the fluid flow and
one for the structure.
In Step 4, the step length # (k) is determined using a standard line search technique
[7] based on the function
More precisely, we first compute the initial reduction
Jp (k) .
Then, # (k) is picked such that
Here # is a pre-selected parameter (use The standard cubic backtracking
algorithm [7] is used in our computations.
5. Numerical experiments. We show a few numerical experiments in this
section using ASPIN, and compare with the results obtained using a standard inexact
Newton's algorithm. We are mostly interested in the kind of problems on which
the regular inexact Newton type algorithm does not work well. We shall focus our
discussion on the following two-dimensional driven cavity flow problem [15], using
the velocity-vorticity formulation, in terms of the velocity u, v, and the vorticity #,
x
y
Fig. 5.1. A 9 - 9 fine mesh with 3 - 3 subdomain partition. The 'o' are the mesh points. The
dashed lines indicate a 3 - nonoverlapping partitioning. The solid lines indicate
the "overlapping = 1" subdomains.
defined on the unit
-#u-
#y
#x
Re
#x
#y
Here Re is Reynolds number. The boundary conditions are:
. bottom, left and right:
. top:
We vary the Reynolds number in the experiments. The boundary condition on # is
given by its definition:
#y
#x
The usual uniform mesh finite di#erence approximation with the 5-point stencil is
used to discretize the boundary value problem. Upwinding is used for the divergence
(convective) terms and central di#erencing for the gradient (source) terms. To obtain
a nonlinear algebraic system of equations F , we use natural ordering for the mesh
points, and at each mesh point, we arrange the knowns in the order of u, v, and #.
The partitioning of F is through the partitioning of the mesh points. In other words,
the partition is neither physics-based nor element-based. Figure 5.1 shows a typical
mesh, together with an overlapping partition. The subdomains may have di#erent
sizes depending on whether they touch the boundary of # The size of the overlap is
as indicated in Figure 5.1. Note that since this is mesh-point based partition, the zero
overlap case in fact corresponds to the 1/2 overlap case of the element-based partition,
which is used more often in the literature on domain decomposition methods for finite
element problems [10].
The subdomain Jacobian matrices JS i
are formed using a multi-colored finite
di#erence scheme.
The implementation is done using PETSc [1], and the results are obtained on a
cluster of DEC workstations. Double precision is used throughout the computations.
We report here only the machine independent properties of the algorithms.
5.1. Parameter definitions. We stop the global PIN iterations if
used for all the tests. The global linear iteration for solving
the global Jacobian system is stopped if the relative tolerance
or the absolute tolerance
is satisfied. In fact we pick # independent of k, throughout the
nonlinear iterations. Several di#erent values of # global-linear-rtol are used as given in
the tables below.
At the kth global nonlinear iteration, nonlinear subsystems
defined in Step 1 a) of Algorithm 4.1, have to be solved. We use the standard IN with
a cubic line search for such systems with initial guess g (k)
0. The local nonlinear
iteration in subdomain S i is stopped if one of the following two conditions is satisfied:
)# local-nonlinear-rtol #FS i
or
)# local-nonlinear-atol .
The overall cost of the algorithm depends heavily on the choice of # local-nonlinear-rtol .
We report computation results using a few di#erent values for it.
5.2. Comparison with a Newton-Krylov-Schwarz algorithm. We compare
the newly developed algorithm ASPIN with a well-understood inexact Newton
algorithm using a cubic backtracking line search as the global strategy, as described
in [7]. Since we would like to concentrate our study on the nonlinear behavior of the
algorithm, not how the linear Jacobian systems are solved, the Jacobian systems are
solved almost exactly at all Newton iterations. More precisely at each IN iteration,
the Newton direction p (k) satisfies
with GMRES with an one-level additive Schwarz preconditioner is used
as the linear solver with the same partition and overlap as in the corresponding ASPIN
algorithm. The history of nonlinear residuals is shown in Figure 5.2 (top) with several
di#erent Reynolds numbers on a fixed fine mesh of size 128 - 128.
5.3. Test results and observations. As the Reynolds number increases, the
nonlinear system becomes more and more di#cult to solve. The Newton-Krylov-
Schwarz algorithm fails to converge once the Reynolds number passes the value
770.0 on this 128 - 128 mesh, no matter how accurately we solve the Jacobian
system. Standard techniques for going further would employ pseudo time
stepping [18] or nonlinear continuation in h or Re [28]. However, our proposed PIN
algorithm converges for a much larger range of Reynolds numbers as shown in Figure
5.2. Furthermore, the number of PIN iterations does not change much as we increase
the Reynolds number. A key to the success of the method is that the subdomain
nonlinear problems are well solved.
In

Table

5.1, we present the numbers of global nonlinear PIN iterations and the
numbers of global GMRES iterations per PIN iteration for various Reynolds numbers
and overlapping sizes. Two key stopping parameters are # global-linear-rtol for the
global linear Jacobian systems and # local-nonlinear-rtol for the local nonlinear systems.
We test several combinations of two values 10 -6 and 10 -3 . As shown in the table, the
total number of PIN iteration does not change much as we change # global-linear-rtol
and # local-nonlinear-rtol ; however, it does increase from 2 or 3 to 6 or 9 when the
Reynolds number increases from 1 to 10 4 . The bottom part of Table 5.1 shows the
corresponding numbers of GMRES iterations per PIN iteration. These linear iteration
numbers change drastically as we switch to di#erent stopping parameters. Solving the
global Jacobian too accurately will cost a lot of GMRES iterations and not result in
much savings in the total number of PIN iterations.

Table

5.1 also compares the results with two sizes of overlap. A small number
PIN iterations can be saved as one increases the overlapping size from 0 to 1, or more,
as shown also in Table 5.3. The corresponding number of global linear iterations
decreases a lot. We should mention that the size of subdomain nonlinear systems
increases as one increases the overlap, especially for three dimensional problems. The
communication cost in a distributed parallel implementation also increases as we
increase the overlap. Recent experiments seem to indicate that small overlap, such as
overlap=1, is preferred balancing the saving of the computational cost and the increase
of the communication cost, see for example [10, 14]. Of course, the observation is
highly machine and network dependent.
In

Table

5.2, we look at the number of Newton iterations for solving the subdomain
nonlinear systems. In this test case, we partition the domain into 16 subdomains,
4 in each direction, and number them naturally from the bottom to top, and left to
right. Four
touch the moving lid. The solution
of the problem is less smooth near the lid, especially when the Reynolds number is
large. As expected, the subdomains near the lid need more iterations; two to three
times more than what is needed in the smooth subdomains for the large Reynolds
number cases.
We next show how the iteration numbers change as we change the number of
subdomains with a fixed 128 - 128 fine mesh. The results are displayed in Table
5.4. As we increase the number of subdomains from 4 to 16 the number of global
PIN iterations does not change much; up or down by 1 is most likely due to the last
bits of the stopping conditions rather than the change of the algorithm. Note that
when we change the number of subdomains, the inexact Newton direction changes,
and as a result, the algorithm changes. As a matter of fact, we are comparing two
mathematically di#erent algorithms. The bottom part of Table 5.4 shows that the
number of GMRES iterations per PIN increases quite a bit as we increase the number
Global PIN iterations. Fine mesh 128 - 128, 4 - 4 subdomain partition on 16 processors.
Subdomain linear systems are solved exactly. # global-linear-rtol is the stopping condition for the
global GMRES iterations. # local-nonlinear-rtol is the stopping condition for the local nonlinear
iterations. The absolute tolerances are #
. The finite di#erence step size is 10 -8 .
number of PIN iterations
number of GMRES iterations per PIN
of subdomains.
6. Some further comments. We comment on a few important issues about
the newly proposed algorithm including parallel scalabilities and load balancing in
parallel implementations.
Parallel scalability is a very important issue when using linear or nonlinear iterative
methods for solving problems with a large number of unknowns on machines
with a large number of processors. It usually involves two separate questions, namely
how the iteration numbers change with the number of processors and with the number
of unknowns. It is a little bit surprising that, from our limited experience, the
number of ASPIN iterations is not sensitive at all to either the number of processors
or the number of unknowns. In other words, the number of nonlinear PIN iterations
is completely scalable. However, this can not be carried over to the linear solver. To
Total number of subdomain nonlinear iterations. Fine mesh 128 - 128, 4 - 4 subdomain partition
on processors. Subdomains are naturally ordered. Subdomain linear systems are solved
exactly. # is the stopping condition for the global GMRES iterations.
is the stopping condition for the local nonlinear iterations. The absolute
tolerances are # 1. The
finite di#erence step size is 10 -8 .
subdomain #

Table
Varying the overlapping size. Fine mesh 128 - 128, 4 - 4 subdomain partition on 16 pro-
cessors. Subdomain linear systems are solved exactly. # is the stopping
condition for the global GMRES iterations. # is the stopping condition
for the local nonlinear iterations. The absolute tolerances are #
. The finite di#erence step size is 10 -8 .
GMRES/PIN
make the linear solver scalable, a coarse grid space is definitely needed. Our current
software implementation is not capable of dealing with the coarse space, therefore no
further discussion of this issue can be o#ered at this point.
Load balancing is another important issue for parallel performance that we do not
address in the paper. As shown in Table 5.2, the computational cost is much higher
in the subdomains near the lid than the other subdomains, in particular for the
large Reynolds number cases. To balance the computational load, idealy, one should
partition the domain such that these subdomains that require more linear/nonlinear
iterations contain less mesh points. However, the solution dependent cost information
is not available until after a few iterations, and therefore the ideal partition has to
obtained dynamically as the computation is being carried out.
Di#erent subdomain partitions with the same fine mesh 128 - 128. Subdomain linear systems
are solved exactly. # is the stopping condition for the global GMRES
iterations. # is the stopping condition for the local nonlinear iterations.
The absolute tolerances are #
1. The finite di#erence step size is 10 -8 .
number of PIN iterations
subdomain partition
number of GMRES iterations per PIN

Table
Di#erent fine meshes on 16 processors. Subdomain linear systems are solved ex-
actly. # is the stopping condition for the global GMRES iterations.
is the stopping condition for the local nonlinear iterations. The absolute
tolerances are # 1. The
finite di#erence step size is 10 -8 .
number of PIN iterations
fine mesh
number of GMRES iterations per PIN
We only discussed one partitioning strategy based on the geometry of the mesh
and the number of processors available in our computing system. Many other partitioning
strategies need to be investigated. For example, physics-based partitions: all
the velocity unknowns
as# 1 and the vorticity unknowns
. In this case, the number
of subdomains may have nothing to do with the number of processors. Further
partitions may be needed on
and# 2 for the purpose of parallel process-
ing. One possible advantage of this physics-based partition is that the nonlinearities
between di#erent physical quantities can be balanced.
An extreme case of a mesh-based partition would be that each subdomain contains
only one grid point. Then, the dimension of the subdomain nonlinear system is the
same as the number of variables associated with a grid point, 3 for our test case. In
this situation, ASPIN becomes a pointwise nonlinear scaling algorithm. As noted in
linear scaling does not change the nonlinear convergence of Newton's method, but
nonlinear scaling does. Further investigation should be of great interest.



--R

The Portable
Hybrid Krylov methods for nonlinear systems of equations
Convergence theory of nonlinear Newton-Krylov algorithms
Parallel Newton- Krylov-Schwarz algorithms for the transonic full potential equation
Domain decomposition methods for monotone nonlinear elliptic problems
Nonlinearly preconditioned Krylov subspace methods for discrete Newton algorithms
Numerical Methods for Unconstrained Optimization and Nonlinear Equations

On the nonlinear domain decomposition method
Domain decomposition algorithms with small overlap
Globally convergent inexact Newton methods
Choosing the forcing terms in an inexact Newton method
Matrix Computations
Globalized Newton-Krylov- Schwarz algorithms and software for parallel implicit CFD
Numerical Computation of Internal and External Flows
Robust linear and nonlinear strategies for solution of the transonic Euler equations
Iterative Methods for Linear and Nonlinear Equations
Convergence analysis of pseudo-transient continuation
An analysis of approximate nonlinear elim- ination
On the Schwarz alternating method.
On the Schwarz alternating method.
On Schwarz alternating methods for incompressible Navier-Stokes equations in n dimensions

NITSOL: A Newton iterative solver for nonlinear systems
Parallel Multilevel Methods for Elliptic Partial Di
Rate of convergence of some space decomposition methods for linear and nonlinear problems
Global convergence of inexact Newton methods for transonic flow
A locally refined rectangular grid finite element method: Application to computational fluid dynamics and computational physics
--TR

--CTR
Feng-Nan Hwang , Xiao-Chuan Cai, A parallel nonlinear additive Schwarz preconditioned inexact Newton algorithm for incompressible Navier-Stokes equations, Journal of Computational Physics, v.204
Heng-Bin An , Ze-Yao Mo , Xing-Ping Liu, A choice of forcing terms in inexact Newton method, Journal of Computational and Applied Mathematics, v.200 n.1, p.47-60, March, 2007
S.-H. Lui, On monotone iteration and Schwarz methods for nonlinear parabolic PDEs, Journal of Computational and Applied Mathematics, v.161 n.2, p.449-468, 15 December
D. A. Knoll , D. E. Keyes, Jacobian-free Newton-Krylov methods: a survey of approaches and applications, Journal of Computational Physics, v.193 n.2, p.357-397, 20 January 2004
incompressible flows;nonlinear preconditioning;nonlinear additive Schwarz;inexact Newton methods;krylov subspace methods;domain decomposition;nonlinear equations;parallel computing