טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDardyk Gregory
SubjectRobust Nonlinear Multigrid Methods
DepartmentDepartment of Computer Science
Supervisor Professor Irad Yavneh


Abstract

Multigrid methods for nonlinear partial differential equations (PDE) are studied. We first analyze the advantages and the disadvantages of the two classical approaches: Global Linearization, such as Newton's method, and Local Linearization, such as the Full Approximation Scheme (FAS). Then we present the novel Multilevel Nonlinear Method (MNM), that enjoys the advantages of the two classical approaches, while overcoming the disadvantages. The new method is tested using one-dimensional and two-dimensional problems and proves to perform significantly better than the two classical approaches. An adaptive variant of MNM is also presented, that is expected to provide even better performance when both adaptive parameters are optimized.


We then apply the same three algorithms to the real-world problem of two-dimensional phase unwrapping. The problem is an essential part of many coherent signal processing applications, for example, Interferometric Synthetic Aperture Radar (SAR). Due to the nature of SAR imaging, SAR images do not contain information about the absolute phase of the returning radar echoes. Instead, the phase is wrapped into the interval [-π, π]. Using the minimum Lp-norm approach, we apply the Multigrid algorithms for reconstructing surfaces from their "wrapped" values. Multigrid algorithms have previously been considered and applied to the problem only for the linear problems arising from the use of the L2 norm. Here, we apply these methods to the nonlinear problems that arise from the Lp norm formulation for p<2. The methods prove to be efficient even for difficult problems with noisy and discontinuous images. The new method, MNM, exhibits the fastest and most robust convergence of the three, given an appropriate choice of a damping parameter. This parameter is determined automatically on very coarse grids at a small computational cost.