Parallel detection of subsystems in linear systems arising in the MESHFREE finite pointset method

Abstract

The Finite Pointset Method (FPM) is a meshfree method for simulations in the field of fluid dynamics and continuum mechanics (Tiwari and Kuhnert, Finite pointset method based on the projection method for simulations of the incompressible Navier-Stokes equations. Springer, Berlin, 2003). The key idea in FPM is to discretize the necessary differential operators by using stencils generated by a least squares approach on a pointcloud that is moving in every time step. Applying Algebraic Multigrid Methods (AMG) to the linear systems arising in FPM comes with various challenges, see our previous work Metsch et al. (Comput Vis Sci, reviewed) and Nick et al. (Linear solvers for the finite pointset method. In: Schäfer, M., Behr, M., Mehl, M., Wohlmuth, B. (eds.) Recent advances in computational engineering. Springer, Cham, 2018). In Nick et al. (Linear solvers for the finite pointset method. In: Schäfer, M., Behr, M., Mehl, M., Wohlmuth, B. (eds.) Recent advances in computational engineering. Springer, Cham, 2018) we limited ourselves to essentially irreducible matrices, saying that if a matrix arising from FPM is not essentially irreducible, we can employ a parallel algorithm in order to detect those subsystems that are essentially irreducible. This paper introduces the algorithm that we use in order to detect independent parts of the FPM pointcloud, which we call components. The algorithm that we propose has a theoretical complexity of O(|V|) in the average case, where |V | is the number of points in the pointcloud. Our experiments with a real world model however show that in practice the complexity is much better. The experiments also show that in order to guarantee a stable convergence of the arising linear systems, detecting components is essential, as singular components can occur in certain situations. Finally, we give an outlook on how our handling of the components could be improved in the future.