Algorithms for fast simulations of space-time adaptive finite element methods

Abstract

Symulacje komputerowe do rozwiązywania problemów niestacjonarnych są szeroko stosowane w wielu zagadnieniach inżynieryjnych, począwszy od symulacji z dziedziny inżynierii materiałowej, geologii, poprzez symulacje wypadków samochodowych, aż do symulacji biomedycznych. Klasyczne algorytmy do rozwiązywania problemów niestacjonarnych stosują schemat jawny Eulera lub schematy niejawne typu Cranka-Nicolsona do rozwiązywania poszczególnych kroków czasowych w pętli. Możliwe jest stosowanie adaptacji w poszczególnych krokach czasowych, jak również stosowanie adaptacyjnych schematów całkowania w dziedzinie czasowej. Wszystkie te podejścia wymagają rozwiązania problemu przestrzennego na sekwencji adaptacyjnych siatek obliczeniowych w poszczególnych krokach czasowych. Podejście alternatywne polega na generacji siatki adaptacyjnej w dziedzinie czasoprzestrzennej. Podejście to umożliwia stosowanie krótszych kroków czasowych w jednym obszarze siatki przestrzennej oraz dłuższych kroków czasowych w innym obszarze przestrzennym. W niniejszej pracy doktorskiej oszacowana została złożoność obliczeniowa solwerów na wielowymiarowych siatkach adaptacyjnych. W szczególności porównano koszty obliczeniowe rozwiązywania problemów niestacjonarnych rozwiązywanych na adaptacyjnych siatkach czasoprzestrzennych z kosztami obliczeniowymi solwerów rozwiązujących problem niestacjonarny za pomocą schematu iteracyjnego na sekwencji adaptacyjnych siatek obliczeniowych w dziedzinie przestrzennej. Zaproponowano również algorytm solwera dokładnego o quasi-optymalnej złożoności obliczeniowej na wielowymiarowych siatkach obliczeniowych. Computer simulations for solving non-stationary problems are widely used in a wide range of engineering problems, from simulations in materials engineering, geology, through simulations of automobile accidents to biomedical simulations. Classical algorithms for solving non-stationary problems use an explicit Euler scheme or implicit Crank-Nicolson type schemes to solve individual time steps in a loop. It is possible to use adaptation in individual time steps, as well as to use adaptive integration schemes in the time domain. All these approaches require solving the spatial problem on a sequence of adaptive computational grids at individual time steps. An alternative approach is to generate an adaptive mesh in the time-space domain. This approach allows the use of shorter time steps in one spatial grid area and longer time steps in another spatial area. In this dissertation, the computational complexity of solvers on multidimensional adaptive grids was estimated. In particular, the computational cost of solving non-stationary problems solved on adaptive time-space grids was compared with the computational cost of solvers solving a non-stationary problem using an iterative scheme on a sequence of adaptive grids in the spatial domain. An exact solver algorithm with quasi-optimal computational complexity on multidimensional computational grids is also proposed.