996
A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF
THE REQUIREMENTS FOR THE DEGREE OF
Doctor of Philosophy
in
THE FACULTY OF GRADUATE STUDIES
(Department of Computer Science)
We accept this thesis as conforming
to the required standard
The University of British Columbia
August 2001
c Dhavide Arjunan Aruliah, 2001 Abstract
The speed of iterative solvers for discretizations of partial dierential
equations (PDEs) is a signicant bottleneck in the performance of codes de-
signed to solve large-scale electromagnetic inverse problems. A single data in-
version requires solving Maxwells equations dozens if not hundreds of times.
An inherent diculty in geophysical contexts is that the conductivity and
permeability coecients may exhibit discontinuities spanning several orders
of magnitude. Furthermore, in the air, the conductivity eectively vanishes.
In standard formulations of Maxwells equations, the curl operator that dom-
inates the PDE operator leads to strong mixing of eld components and ill-
conditioning of linear systems resulting from standard discretizations.
The primary objective of this research is to build fast iterative solvers for
the forward-modeling problem associated with electromagnetic inverse prob-
lems in the frequency domain. Toward this goal, a Helmholtz decomposition of
the electric eld using a Coulomb gauge condition recasts the PDE problem in
terms of scalar and vector potentials. The resulting indenite system is then
stabilized by addition of a vanishing term that lies in the kernel of the domi-
nant curl operator. Finally, an extra dierentiation recasts the PDE system
in a diagonally-dominant form reminiscent of a pressure-Poisson formulation
for incompressible uid ow. The continuous PDE problem obtained is equiv-
alent to the original Maxwells system but has a structure that is amenable to
reliable solution techniques.
Using a nite-volume scheme, the PDE is discretized on a staggered
grid in three dimensions. The discretization obtained possesses conservation
properties typical of nite-volume methods. Furthermore, interface conditions
imposed by discontinuities in the material coecients are sensibly accounted
for in deriving the discretization. Although the simple representation of the
ii media on a Cartesian tensor-product grid uses staircase approximations of
surfaces of discontinuity of the material coecients, some analysis and a nu-
merical study demonstrate the suitability of such coarse approximations for
diusive problems.
The discretization yields a non-Hermitian sparse linear system of al-
gebraic equations; various preconditioners for Krylov-subspace methods are
described, analyzed, implemented, and tested. Of particular interest is a
multigrid preconditioner that exploits both the structure of the PDE prob-
lem and the availability of well-established solvers for elliptic PDE problems
(in particular, Dendys BOXMG solver). The end result is a robust solver for
the forward-modeling equations that can be incorporated within a competitive
inverse problem code.
iii Contents
Abstract
ii
Contents
iv
List of Tables
vii
List of Figures
viii
Acknowledgements
ix
Dedication
x
1
Introduction
1
1.1
Background Sketch . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Outline of research . . . . . . . . . . . . . . . . . . . . . . . .
9
2
Background Theory of Electromagnetism
14
2.1
Maxwells Equations . . . . . . . . . . . . . . . . . . . . . . .
14
2.2
Derived Models . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.2.1
Constitutive Relations . . . . . . . . . . . . . . . . . .
17
iv 2.2.2
Stationary Models: Electrostatics and Magnetostatics .
19
2.2.3
The Time-Harmonic Model . . . . . . . . . . . . . . .
21
2.2.4
The Quasistatic Model . . . . . . . . . . . . . . . . . .
22
2.2.5
Electric Source Currents . . . . . . . . . . . . . . . . .
23
2.2.6
Magnetic Source Currents . . . . . . . . . . . . . . . .
25
2.2.7
The Magnetotelluric Model . . . . . . . . . . . . . . .
26
2.3
Boundary Conditions . . . . . . . . . . . . . . . . . . . . . . .
29
2.3.1
Frequency-Domain Boundary Conditions . . . . . . . .
31
2.3.2
Interface Conditions . . . . . . . . . . . . . . . . . . .
33
2.4
Second-order PDE Formulations . . . . . . . . . . . . . . . . .
36
2.5
Weak Formulations . . . . . . . . . . . . . . . . . . . . . . . .
38
3
Vector and Scalar Potential Formulations
43
3.1
The Forward-modeling Problem . . . . . . . . . . . . . . . . .
44
3.1.1
Helmholtz Decomposition . . . . . . . . . . . . . . . .
47
3.1.2
Stabilization . . . . . . . . . . . . . . . . . . . . . . . .
49
3.1.3
Pressure-Poisson Formulation . . . . . . . . . . . . .
50
3.2
Boundary Conditions . . . . . . . . . . . . . . . . . . . . . . .
53
3.2.1
Interface Conditions . . . . . . . . . . . . . . . . . . .
59
3.3
Weak Formulations . . . . . . . . . . . . . . . . . . . . . . . .
61
4
Finite-Volume Discretizations
63
4.1
Domain of Discretization . . . . . . . . . . . . . . . . . . . . .
63
4.2
The Yee Discretization . . . . . . . . . . . . . . . . . . . . . .
66
4.2.1
The Discrete Fields . . . . . . . . . . . . . . . . . . . .
68
v 4.2.2
Derivation of Yee Scheme . . . . . . . . . . . . . . . .
70
4.3
Discretization Using Potentials . . . . . . . . . . . . . . . . . .
74
4.3.1
The Discrete Fields . . . . . . . . . . . . . . . . . . . .
76
4.3.2
Derivation of the Finite-Volume Scheme . . . . . . . .
78
4.3.3
The Discrete Linear System . . . . . . . . . . . . . . .
84
4.4
Grid Eects . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
4.4.1
Model Problem Analysis . . . . . . . . . . . . . . . . .
89
4.4.2
Numerical Study . . . . . . . . . . . . . . . . . . . . .
95
5
Construction and Analysis of Iterative Solvers
103
5.1
Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . .
104
5.1.1
Preconditioned Krylov-Subspace Methods . . . . . . .
104
5.2
Analytical Framework . . . . . . . . . . . . . . . . . . . . . .
110
5.2.1
Discrete Operators on a Periodic Grid . . . . . . . . .
111
5.3
Spectral Bounds . . . . . . . . . . . . . . . . . . . . . . . . . .
114
5.4
Numerical Experiments . . . . . . . . . . . . . . . . . . . . . .
121
6
Conclusions
132
6.1
Research Summary . . . . . . . . . . . . . . . . . . . . . . . .
132
6.2
Future Research . . . . . . . . . . . . . . . . . . . . . . . . . .
136
Bibliography
139
vi List of Tables
2.1
Field quantities in Maxwells equations. . . . . . . . . . . . . .
15
2.2
Constitutive parameters for Maxwells equations. . . . . . . .
18
4.1
=
HS
: results with vertical shifts . . . . . . . . . . . . . . .
98
4.2
=
E
: results with vertical shifts . . . . . . . . . . . . . . . .
100
4.3
=
E
: results with ne & coarse resolutions . . . . . . . . .
102
5.1
=
B
and electric dipole source on uniform grids. . . . . . .
125
5.2
=
B
and electric dipole source on nonuniform grids. . . . .
126
5.3
=
B
and magnetic dipole source on uniform grids. . . . . .
127
5.4
=
B
and magnetic dipole source on nonuniform grids. . . .
127
5.5
=
E
and electric dipole source on uniform grids. . . . . . .
128
5.6
=
B
over a range of frequencies. . . . . . . . . . . . . . . .
128
vii List of Figures
2.1
Innitesimal volume V for interface conditions . . . . . . . . .
34
3.1
A typical geophysical scenario . . . . . . . . . . . . . . . . . .
45
4.1
Primary and dual grids for discretization . . . . . . . . . . . .
66
4.2
Staggering of components of E
h
for Yee scheme . . . . . . . .
70
4.3
Staggering of components of H
h
for Yee scheme . . . . . . . .
71
4.4
Cross-sections of , , and the support S
h
of
. . . . . . 91
4.5
Cross-sections of
HS
and
E
. . . . . . . . . . . . . . . . . . .
97
4.6
Cross-sections of
E
resolved on ne and coarse grids. . . . . .
99
5.1
Eigenvalue range and condition number vs.
. . . . . . . . .
119
5.2
Cross-section of
B
. . . . . . . . . . . . . . . . . . . . . . . .
124
5.3
Comparison of AMG and M
M
. . . . . . . . . . . . . . . . . .
131
viii Acknowledgements
I have many people to thank. To start, the sta and members of the
Dept. of Computer Science and the Institute of Applied Mathematics at UBC
have been wonderfully helpful. I oer thanks also to my friends; too many to
list, they know who they are. And of course, my family has always given me
unconditional love and support without which I could not have gotten so far.
My graduate experiences have taught me much about scientic inquiry
and collaboration. I want to thank the members of the Scientic Computation
and Visualization group as well as the UBC-GIF for greatly broadening my
perspective. Drs. David Moulton and Joel Dendy assisted me greatly with
the generous loan of their codes, as did Dr. Yair Shapira. I thank Drs. Doug
Oldenburg, Jim Varah, and Brian Wetton for their helpful advice as members
of my supervisory committee. I am also deeply grateful for the unbounded
enthusiasm and scientic insight of my friend and colleague Dr. Eldad Haber.
It is encouraging that the spirit of cooperation and camaraderie thrives in my
scientic peers in spite of other pressures.
Finally, I am extremely indebted to my research supervisor, Dr. Uri
Ascher. He has set an example as a scientic researcher, as a teacher, and as
a person that will be dicult to live up to in my future career. His support,
guidance, inspiration, and friendship have been essential through dicult times
over the last few years. Thank you, Uri, for everything.
Dhavide Arjunan Aruliah
The University of British Columbia
August 2001
ix To my mothers parents,
Daniel Chellathurai Arulanantham and
Grace Emily