Search

We consider effective preconditioners for solving Laplacians of general weighted graphs. Theoretically, spectral sparsifiers (SSs) provide preconditioners of optimal computational complexity. However, they are not easy to use for real-world applications due to implementation complications. Multigrid methods, on the contrary, are computationally efficient but lack theoretical justification. To bridge the gap between theory and practice, we adopt ideas of multigrid and SS methods and proposed preconditioners that can be used in practice with theoretical guarantees. We expand the original graph based on a multilevel structure to obtain an equivalent expanded graph. Although the expanded graph has a low diameter, a favorable property for constructing SSs, it has negatively weighted edges, which is an unfavorable property for SSs. We design an algorithm to properly eliminate the negatively weighted edges and prove that the resulting expanded graph with positively weighted edges is spectrally equivalent to the expanded graph and, thus, the original graph. Due to the low-diameter property of the positively weighted expanded graph preconditioner (PEGP), existing algorithms for finding SSs can be easily applied. To demonstrate the advantage of working with PEGP, we propose a type of SS, the multilevel graph sparsifier preconditioner (MGSP), that can be constructed in an easy and deterministic manner. We provide some preliminary numerical experiments to verify our theoretical findings and illustrate the practical effectiveness of PEGP and MGSP in real-world applications. [ABSTRACT FROM AUTHOR]

This paper concerns numerical solution of the diffusion equation with strong anisotropy on meshes not aligned with the anisotropic vector field. In order to resolve the numerical pollution for simulations on a non-anisotropy-aligned mesh and reduce the associated high computational cost we propose an effective preconditioner, extending our previous work [D. Green et al., Comput. Phys. Commun., 9 (2022), 108333]. Similar to the anisotropy-aligned mesh case, we apply the auxiliary space preconditioning framework to design a preconditioner where a continuous finite element space is used as the auxiliary space for the discontinuous finite element space. The key component is an effective line smoother that can mitigate the high-frequency errors perpendicular to the magnetic field. We design a graph-based approach to find such a line smoother that is approximately perpendicular to the vector fields when the mesh does not align with the anisotropy. Numerical experiments for several benchmark problems are presented, demonstrating the effectiveness and robustness of the proposed preconditioner when applied to Krylov iterative methods. [ABSTRACT FROM AUTHOR]