Ludmil T. Zikatanov

Xiaozhe Hu, Carmen Rodrigo, Francisco J. Gaspar et al.

A stable finite element scheme that avoids pressure oscillations for a three-field Biot's model in poroelasticity is considered. The involved variables are the displacements, fluid flux (Darcy velocity), and the pore pressure, and they are discretized by using the lowest possible approximation order: Crouzeix-Raviart finite elements for the displacements, lowest order Raviart-Thomas-Nedelec elements for the Darcy velocity, and piecewise constant approximation for the pressure. Mass lumping technique is introduced for the Raviart-Thomas-Nedelec elements in order to eliminate the Darcy velocity and, therefore, reduce the computational cost. We show convergence of the discrete scheme which is implicit in time and use these types of elements in space with and without mass lumping. Finally, numerical experiments illustrate the convergence of the method and show its effectiveness to avoid spurious pressure oscillations when mass lumping for the Raviart-Thomas-Nedelec elements is used.

Raytcho D. Lazarov, Ludmil T. Zikatanov

This paper contains construction and analysis a finite element approximation for convection dominated diffusion problems with full coefficient matrix on general simplicial partitions in $R^d$, $d=2,3$. This construction is quite close to the scheme of Xu and Zikatanov (Math. Comp. 1999) where a diagonal coefficient matrix has been considered. The scheme is of the class of exponentially fitted methods that does not use upwind or checking the flow direction. It is stable for sufficiently small discretization step-size assuming that the boundary value problem for the convection-diffusion equation is uniquely solvable. Further, it is shown that, under certain conditions on the mesh the scheme is monotone. Convergence of first order is derived under minimal smoothness of the solution.

Randolph E. Bank, Panayot S. Vassilevski, Ludmil T. Zikatanov

This note proposes embedding a time dependent PDE into a convection-diffusion type PDE (in one space dimension higher) with singularity, for which two discretization schemes, the classical streamline-diffusion and the EAFE (edge average finite element) one, are investigated in terms of stability and error analysis. The EAFE scheme, in particular, is extended to be arbitrary order which is of interest on its own. Numerical results, in combined space-time domain demonstrate the feasibility of the proposed approach.

Carmen Rodrigo, Francisco J. Gaspar, Ludmil T. Zikatanov

Local Fourier analysis (LFA) is a useful tool in predicting the convergence factors of geometric multigrid methods (GMG). As is well known, on rectangular domains with periodic boundary conditions this analysis gives the exact convergence factors of such methods. In this work, using the Fourier method, we extend these results by proving that such analysis yields the exact convergence factors for a wider class of problems.

Xiaozhe Hu, Junyuan Lin, Ludmil T. Zikatanov

We propose a path cover adaptive algebraic multigrid (PC-$α$AMG) method for solving linear systems of weighted graph Laplacians and can also be applied to discretized second order elliptic partial differential equations. The PC-$α$AMG is based on unsmoothed aggregation AMG (UA-AMG). To preserve the structure of smooth error down to the coarse levels, we approximate the level sets of the smooth error by first forming vertex-disjoint path cover with paths following the level sets. The aggregations are then formed by matching along the paths in the path cover. In such manner, we are able to build a multilevel structure at a low computational cost. The proposed PC-$α$AMG provides a mechanism to efficiently re-build the multilevel hierarchy during the iterations and leads to a fast nonlinear multilevel algorithm. Traditionally, UA-AMG requires more sophisticated cycling techniques, such as AMLI-cycle or K-cycle, but as our numerical results show, the PC-$α$AMG proposed here leads to nearly optimal standard V-cycle algorithm for solving linear systems with weighted graph Laplacians. Numerical experiments for some real world graph problems also demonstrate PC-$α$AMG's effectiveness and robustness, especially for ill-conditioned graphs.

James H. Adler, Xiaozhe Hu, Ludmil T. Zikatanov

In this paper, we design robust and efficient linear solvers for the numerical approximation of solutions to Maxwell's equations with dissipative boundary conditions. We consider a structure-preserving finite-element approximation with standard Nedelec--Raviart--Thomas elements in space and a Crank--Nicolson scheme in time to approximate the electric and magnetic fields. We focus on two types of block preconditioners. The first type is based on the well-posedness results of the discrete problem. The second uses an exact block factorization of the linear system, for which the structure-preserving discretization yields sparse Schur complements. We prove robustness and optimality of these block preconditioners, and provide supporting numerical tests.

John C. Urschel, Ludmil T. Zikatanov

Spectral graph bisections are a popular heuristic aimed at approximating the solution of the NP-complete graph bisection problem. This technique, however, does not always provide a robust tool for graph partitioning. Using a special class of graphs, we prove that the standard spectral graph bisection can produce bisections that are far from optimal. In particular, we show that the maximum error in the spectral approximation of the optimal bisection (partition sizes exactly equal) cut for such graphs is bounded below by a constant multiple of the order of the graph squared.

Wenfang Xu, Ludmil T. Zikatanov

We generalize some of the functional (hyper-circle) a posteriori estimates from finite element settings to general graphs or Hilbert space settings. We provide several theoretical results in regard to the generalized a posteriori error estimators. We use these estimates to construct aggregation based coarse spaces for graph Laplacians. The estimator is used to assess the quality of an aggregation adaptively. Furthermore, a reshaping algorithm based is tested on several numerical examples.

Xiaozhe Hu, John C. Urschel, Ludmil T. Zikatanov

Graph disaggregation is a technique used to address the high cost of computation for power law graphs on parallel processors. The few high-degree vertices are broken into multiple small-degree vertices, in order to allow for more efficient computation in parallel. In particular, we consider computations involving the graph Laplacian, which has significant applications, including diffusion mapping and graph partitioning, among others. We prove results regarding the spectral approximation of the Laplacian of the original graph by the Laplacian of the disaggregated graph. In addition, we construct an alternate disaggregation operator whose eigenvalues interlace those of the original Laplacian. Using this alternate operator, we construct a uniform preconditioner for the original graph Laplacian.

James H. Adler, Vesselin Petkov, Ludmil T. Zikatanov

This work is on the numerical approximation of incoming solutions to Maxwell's equations with dissipative boundary conditions whose energy decays exponentially with time. Such solutions are called asymptotically disappearing (ADS) and they play an importarnt role in inverse back-scatering problems. The existence of ADS is a difficult mathematical problem. For the exterior of a sphere, such solutions have been constructed analytically by Colombini, Petkov and Rauch [7] by specifying appropriate initial conditions. However, for general domains of practical interest (such as Lipschitz polyhedra), the existence of such solutions is not evident. This paper considers a finite-element approximation of Maxwell's equations in the exterior of a polyhedron, whose boundary approximates the sphere. Standard Nedelec-Raviart-Thomas elements are used with a Crank-Nicholson scheme to approximate the electric and magnetic fields. Discrete initial conditions interpolating the ones chosen in [7] are modified so that they are (weakly) divergence-free. We prove that with such initial conditions, the approximation to the electric field is weakly divergence-free for all time. Finally, we show numerically that the finite-element approximations of the ADS also decay exponentially with time when the mesh size and the time step become small.

John C. Urschel, Wenfang Xu, Ludmil T. Zikatanov

Analysis of big data has become an increasingly relevant area of research, with data often represented on discrete networks both constructed and organic. While for structured domains, there exist intuitive definitions of signals and frequencies, the definitions are much less obvious for data sets associated with a given network. Often, the eigenvectors of an induced graph Laplacian are used to construct an orthogonal set of low-frequency vectors. For larger graphs, however, the computational cost of creating such structures becomes untenable, and the quality of the approximation is adequate only for signals near the span of the set. We propose a construction of a full basis of frequencies with computational complexity that is near-linear in time and linear in storage. Using this frequency domain, we can compress data sets on unstructured graphs more robustly and accurately than spectral-based constructions.

Katherine Y. Zipp, Yangqingxiang Wu, Kaiyi Wu et al.

Invasive species have been recognized as a leading threat to biodiversity. In particular, lakes are especially affected by species invasions because they are closed systems sensitive to disruption. Accurately controlling the spread of invasive species requires solving a complex spatial-dynamic optimization problem. In this work we propose a novel framework for determining the optimal management strategy to maximize the value of a lake system net of damages from invasive species, including an endogenous diffusion mechanism for the spread of invasive species through boaters' trips between lakes. The proposed method includes a combined global iterative process which determines the optimal number of trips to each lake in each season and the spatial-dynamic optimal boat ramp fee.

James H. Adler, Francisco J. Gaspar, Xiaozhe Hu et al.

In this paper, we design robust and efficient block preconditioners for the two-field formulation of Biot's consolidation model, where stabilized finite-element discretizations are used. The proposed block preconditioners are based on the well-posedness of the discrete linear systems. Block diagonal (norm-equivalent) and block triangular preconditioners are developed, and we prove that these methods are robust with respect to both physical and discretization parameters. Numerical results are presented to support the theoretical results.

Paola F. Antonietti, Marco Sarti, Marco Verani et al.

In this paper we design and analyze a uniform preconditioner for a class of high order Discontinuous Galerkin schemes. The preconditioner is based on a space splitting involving the high order conforming subspace and results from the interpretation of the problem as a nearly-singular problem. We show that the proposed preconditioner exhibits spectral bounds that are uniform with respect to the discretization parameters, i.e., the mesh size, the polynomial degree and the penalization coefficient. The theoretical estimates obtained are supported by several numerical simulations.

John C. Urschel, Xiaozhe Hu, Jinchao Xu et al.

In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalue. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.

Johannes K. Kraus, Panayot S. Vassilevski, Ludmil T. Zikatanov

We derive a three-term recurrence relation for computing the polynomial of best approximation in the uniform norm to $x^{-1}$ on a finite interval with positive endpoints. As application, we consider two-level methods for scalar elliptic partial differential equation (PDE), where the relaxation on the fine grid uses the aforementioned polynomial of best approximation. Based on a new smoothing property of this polynomial smoother that we prove, combined with a proper choice of the coarse space, we obtain as a corollary, that the convergence rate of the resulting two-level method is uniform with respect to the mesh parameters, coarsening ratio and PDE coefficient variation.