Extended convergence analysis for multi-grid algorithms and its application in mobility models

The purpose of this thesis is to extend the Fourier-based convergence theory for multi-grid algorithms. The extension allows an efficient multi-grid algorithm to be configured for situations in which a system shows local variations that cannot be handled by Fourier analysis. The focus of this new convergence analysis is a precise description of aliasing effects on the system and the coarsening strategy of the algorithm. Particular cases where this new analysis can be applied are studied, including systems with square-wave eigen-vectors and mobility models based on correlated random walks.;The application of the convergence analysis to a given system allows one to obtain the factors by which the modal components of the error in one multi-grid iteration are reduced (convergence factors) and mixed (aliasing factors). These factors show the strength and weakness of inter-grid operators used by the algorithm to transfer information between multiple levels of description of a system. Thus, the convergence analysis can be used to evaluate and design efficient inter-grid operators for the application of the multi-grid algorithm.;An application of this theory to models of the mobility of vehicles in a city is considered. An algebraic multi-grid configuration is considered for computation of absorbing times that provide important information for the evaluation of communication protocols in Mobile Ad-hoc NETworks (MANETs). In simple cases, the convergence analysis can be applied to show the efficiency of the configuration and numerical results are provided for more complicated scenarios.