Implicit and multigrid procedures for steady-state computations with upwind algorithms

A computational study for the convergence acceleration of Euler and Navier-Stokes computations with upwind schemes has been conducted in a unified framework. It involves the flux-vector splitting algorithms due to Steger-Warming and Van Leer, the flux-difference splitting algorithms due to Roe and Osher and the hybrid algorithms, AUSM (Advection Upstream Splitting Method) and HUS (Hybrid Upwind Splitting). Implicit time integration with line Gauss-Seidel relaxation and multigrid are among the procedures which have been systematically investigated on an individual as well as cumulative basis. The upwind schemes have been tested in various implicit-explicit operator combinations such that the optimal among them can be determined based on extensive computations for two-dimensional flows in subsonic, transonic, supersonic and hypersonic flow regimes. In this study, the performance of these implicit time-integration procedures has been systematically compared with those corresponding to a multigrid accelerated explicit Runge-Kutta method. It has been demonstrated that a multigrid method employed in conjunction with an implicit time-integration scheme yields distinctly superior convergence as compared to those associated with either of the acceleration procedures provided that effective smoothers, which have been identified in this investigation, are prescribed in the implicit operator.

Multigrid algorithms for symmetric discontinuous Galerkin methods on graded meshes

We study a class of symmetric discontinuous Galerkin methods on graded meshes. Optimal order error estimates are derived in both the energy norm and the L 2 norm, and we establish the uniform convergence of V-cycle, F-cycle and W-cycle multigrid algorithms for the resulting discrete problems. Numerical results that confirm the theoretical results are also presented.

Special Issue on Multigrid Methods

SCOPUS: ed.j

Multigrid for American option pricing with stochastic volatility

The paper describes an implicit finite difference approach to the pricing of American options on assets with a stochastic volatility. A multigrid procedure is described for the fast iterative solution of the discrete linear complementarity problems that result. The accuracy and performance of this approach is improved considerably by a strike-price related analytic transformation of asset prices and adaptive time-stepping.

Anisotropic seismic inversion using a multigrid Monte Carlo approach

We propose a new approach for the inversion of anisotropic P-wave data based on Monte Carlo methods combined with a multigrid approach. Simulated annealing facilitates objective minimization of the functional characterizing the misfit between observed and predicted traveltimes, as controlled by the Thomsen anisotropy parameters (epsilon, delta). Cycling between finer and coarser grids enhances the computational efficiency of the inversion process, thus accelerating the convergence of the solution while acting as a regularization technique of the inverse problem. Multigrid perturbation samples the probability density function without the requirements for the user to adjust tuning parameters. This increases the probability that the preferred global, rather than a poor local, minimum is attained. Undertaking multigrid refinement and Monte Carlo search in parallel produces more robust convergence than does the initially more intuitive approach of completing them sequentially. We demonstrate the usefulness of the new multigrid Monte Carlo (MGMC) scheme by applying it to (a) synthetic, noise-contaminated data reflecting an isotropic subsurface of constant slowness, horizontally layered geologic media and discrete subsurface anomalies; and (b) a crosshole seismic data set acquired by previous authors at the Reskajeage test site in Cornwall, UK. Inverted distributions of slowness (s) and the Thomson anisotropy parameters (epsilon, delta) compare favourably with those obtained previously using a popular matrix-based method. Reconstruction of the Thomsen epsilon parameter is particularly robust compared to that of slowness and the Thomsen delta parameter, even in the face of complex subsurface anomalies. The Thomsen epsilon and delta parameters have enhanced sensitivities to bulk-fabric and fracture-based anisotropies in the TI medium at Reskajeage. Because reconstruction of slowness (s) is intimately linked to that epsilon and delta in the MGMC scheme, inverted images of phase velocity reflect the integrated effects of these two modes of anisotropy. The new MGMC technique thus promises to facilitate rapid inversion of crosshole P-wave data for seismic slownesses and the Thomsen anisotropy parameters, with minimal user input in the inversion process.

Métodos multigrid paralelos em malhas não estruturadas aplicados à simulação de problemas de dinâmica de fluidos computacional e transferência de calor

Fenômenos naturais, tecnológicos e industriais podem, em geral, ser modelados de modo acurado através de equações diferenciais parciais, definidas sobre domínios contínuos que necessitam ser discretizados para serem resolvidos. Dependendo do esquema de discretização utilizado, pode-se gerar sistemas de equações lineares. Esses sistemas são, de modo geral, esparsos e de grande porte, onde as incógnitas podem ser da ordem de milhares, ou até mesmo de milhões. Levando em consideração essas características, o emprego de métodos iterativos é o mais apropriado para a resolução dos sistemas gerados, devido principalmente a sua potencialidade quanto à otimização de armazenamento e eficiência computacional. Uma forma de incrementar o desempenho dos métodos iterativos é empregar uma técnica multigrid. Multigrid são uma classe de métodos que resolvem eficientemente um grande conjunto de equações algébricas através da aceleração da convergência de métodos iterativos. Considerando que a resolução de sistemas de equações de problemas realísticos pode requerer grande capacidade de processamento e de armazenamento, torna-se imprescindível o uso de ambientes computacionais de alto desempenho. Uma das abordagens encontradas na literatura técnica para a resolução de sistemas de equações em paralelo é aquela que emprega métodos de decomposição de domínio (MDDs). Os MDDs são baseados no particionamento do domínio computacional em subdomínios, de modo que a solução global do problema é obtida pela combinação apropriada das soluções obtidas em cada um dos subdomínios Assim, neste trabalho são disponibilizados diferentes métodos de resolução paralela baseado em decomposição de domínio, utilizando técnicas multigrid para a aceleração da solução de sistemas de equações lineares. Para cada método, são apresentados dois estudos de caso visando a validação das implementações. Os estudos de caso abordados são o problema da difusão de calor e o modelo de hidrodinâmica do modelo UnHIDRA. Os métodos implementados mostraram-se altamente paralelizáveis, apresentando bons ganhos de desempenho. Os métodos multigrid mostraram-se eficiente na aceleração dos métodos iterativos, já que métodos que utilizaram esta técnica apresentaram desempenho superior aos métodos que não utilizaram nenhum método de aceleração.

"MGLTSmn" : aproximação angular "multigrid" em uma placa plana

Neste trabalho, desenvolve-se um método “multigrid” para a aproximação angular da solução da equação de transporte de partículas em uma placa plana, baseado na formulação LTSN com dependência contínua na variável angular. Para tanto, aplica-se a formulação LTSN sobre o conjunto de equações SN para determinar o fluxo angular de partículas nas N direções discretas referentes a uma malha grossa (N pequeno) e em seguida, usando os fluxos conhecidos, aplica-se a formulação LTSN com dependência angular contínua, para avaliar o fluxo angular nas M direções discretas referentes a uma malha fina (M grande). São apresentadas simulações numéricas que ilustram a capacidade desse método, denotado por MGLTSMN , no que diz respeito à redução do esforço computacional na aproximação da solução para problemas que requerem elevadas ordens de quadratura e alto grau de anisotropia.