Multigrid methods in network optimization : overview and appraisal
Henson, V. Emden
Bradley, Gordon H.
Rasmussen, Craig W.
MetadataShow full item record
Multigrid methods have been traditionally applied to the solution of certain Partial Differential Equations. However, applications in control theory, optimization, pattern recognition, computational tomography and particle physics are beginning to appear. This thesis analyzes the application of multigrid methodology to optimization problems. The work is centered on networks. Transportation problems are chosen frequently as reference because they have been the object of some multigrid research. The goal is to establish a basis for development of multigrid-based algorithms. Optimality conditions in linear programming and networks are reviewed, and a compilation of various multilevel approaches in optimization is presented. Emphasis is on the recent scaling techniques; they add some special insights into solving large network problems efficiently using progressive level of detail. An analysis of the difficulties that these problems present to the multigrid approach reveals that perhaps some abstraction is appropriate when interpreting multigrid components applied to optimization problems (in particular, the concept of grid itself). The idea of implicit ordering is developed and associated with the effectiveness of the multigrid method. These concepts are applied to identify problems that can be solved using multigrid. Finally, suggestions for the development of future multigrid-based algorithms are provided
Approved for public release; distribution is unlimited.
Showing items related by title, author, creator and subject.
Cavanaugh, Kevin J. (Monterey, California. Naval Postgraduate School, 1992-09);This thesis presents an exploration of the application of multigrid/multilevel techniques to a non-geometric long transportation problem. An introduction to multigrid is given, and specifics of how it is applied to this ...
Volk, John S. (Monterey, California. Naval Postgraduate School, 1994-09);An empirical analysis on the applicability of multigrid techniques to system modeling using system identification techniques is presented. Multigrid with the Toeplitz approximation algorithm is used to model an infinite ...
Cornett, Annette P. (Monterey, California. Naval Postgraduate School, 1993-06);Multigrid methods were developed to solve partial differential equations. Research has shown that these methods are applicable to a broader range of problems. This thesis investigates the application of multigrid techniques ...