ABSTRACT. We introduce the concepts of “gravitational” and “elastic” potential energy in the context of networks and investigate their implications on interpreting certain well-known graph-theoretic parameters and optimization problems. In the case of gravitational potential energy, we treat the nodes of a graph as “particles” with masses and consider the potential energy of gravitational interactions between them. We prove that the maximum clique in a graph represents the minimum gravitational potential energy structure. This result yields a natural physics-based interpretation of the well-known Motzkin-Strauss formulation for the maximum clique problem. In the case of elastic potential energy, we assume that graph nodes are located on an elastic surface, the graph edges represent “springs” connecting the nodes on the surface, and consider the potential energy corresponding to elastic deformations of springs. We show that under certain reasonable assumptions on surface deformation, the second-smallest (i.e., algebraic connectivity) and the largest eigenvalues of the graph Laplacian matrix correspond to the minimum and the maximum elastic potential energies of a graph, respectively. Moreover, the associated eigenvectors correspond to the node heights in the minimum and maximum energy configurations.

ABSTRACT. Cascading phenomena on graphs/networks with sparse adjacency matrices are ubiquitous in various application domains. Perhaps one of the most prominent examples of such applications is propagation of information cascades in social media networks. Simulation and prediction of these time-dependent processes via linear systems and PDEs may yield significant computational costs due to both the size of the respective matrices and the complexity of cascade propagation, which involves uncertainties. In this work, we propose a Euclidean embedding approach for explaining and predicting the propagation of information cascades in networked systems. In the context of social media networks, our model essentially casts social media content-sharing individuals into the space of latent dimensions reflecting their interests, and thus, traits of the content they tend to post and repost. The likelihood maximization problem, formulated to fit the model to observed cascade diffusion data, can be then solved numerically by employing a penalty technique. Computational results, reported with both synthetic and real-world data, showcase the strong predictive power of the proposed model.

ABSTRACT. The intersection of high dimensional simplices may arise in parameter estimation, high dimensional physics and optimization with many parameters. This process can be represented as the sequential intersecting of one simplex with hyperplanes of codimension one. This paper presents some results and techniques to help visualize these high dimensional objects.

ABSTRACT. The Stokes equations, when discretized properly, are known to result in a Schur complement matrix that is spectrally equivalent to the identity matrix, with most of the eigenvalues being equal to one. These facts are the rationales for the famous Uzawa and Krylov-Uzawa iterative algorithms. However, it turns out that for a class of problems where the flow domains are very complicated, e.g., describing pore space in low porosity rocks. The condition number of the Schur complement matrix can become extremely large in such cases, with a spectrum containing large number of non-unit eigenvalues, thus making the Uzawa preconditioner impractical for both cases, without and with Krylov (conjugate gradient) acceleration. In the present talk, we shed light on the reasons behind this ill-conditioning behaviour. Performing systematic study for 3D and 2D problems, we show that the condition number of the Schur complement highly correlates with such a geometric characteristic of the flow domain as the surface-to-volume ratio. For 2D problems we compute the full spectrum for the Schur complement and show that the no-slip boundary conditions are the reason for the non-unit eigenvalues of the Schur complement. Moreover, we show that there is a correlation between number of boundary nodes where no-slip boundary conditions are prescribed, and the number of non-unit eigenvalues for the Schur complement matrix. It is demonstrated that the CG with diffusion-like SIMPLE preconditioner converges rapidly for this class of problems, outperforming the Uzawa preconditioner. Further on, it is shown that the SIMPLE preconditioner converges rapidly also when solving Stokes-Brinkman problem in such geometries. The performance of the AMG preconditioners for solving the blocks in the Uzawa and SIMPLE iterative methods for the Schur complement matrix is also discussed, and it is shown that in certain cases the AMG performance is critical for achieving robust convergence in such complicated geometries.

ABSTRACT. We introduce a novel multilevel formulation of the popular Ensemble Kalman Inversion (EKI) and Ensemble Kalman Sampler (EKS), two interacting particle methods designed for tackling inverse problems, particularly in high-dimensional settings. The EKI and EKS methods are derivative-free, easily parallelizable and empirically give decent results with small ensembles. However, whenever the forward model is expensive to evaluate, the computational cost of the algorithm suffers, because this model has to be evaluated once for every particle at every timestep. Our approach leverages the idea of multilevel Monte Carlo to balance the accuracy and computational cost of different forward models. By utilizing both cheap and precise models in a hierarchical fashion, the algorithm is able to converge faster and with improved accuracy compared to traditional EKI and EKS methods.

ABSTRACT. Scalable approaches for performing Bayesian inference are necessary for characterizing prediction confidence in large-scale PDEs with random coefficients. Many approaches to perform Bayesian inference in this setting are too expensive, e.g., Markov chain Monte Carlo (MCMC). With the increase in problem size and thus high-fidelity (fine grid) simulation cost, MCMC becomes intractable, and acceleration approaches become necessary. One acceleration approach to consider is multilevel MCMC, which accelerates the estimation of fine grid statistical quantities of interest by exploiting a hierarchy of coarse grid (level) discretizations of partial differential equations (PDEs). However current implementations are not suitable to large-scale problems, as the random coefficients are not generated in a scalable manner. In recent work, we developed an algorithmically scalable PDE-based sampling method to generate random coefficient realizations on each level of the multilevel MCMC hierarchy. This was done by using scalable algebraic multigrid methods used in the PDE-sampling. A shortcoming of this approach was that it was not fully scalable due to restrictions on the parallel coarse grids. While this approach demonstrated algorithmic scaling on all levels, full simulation scaling was not achieved across all levels, as the mesh on each level was distributed across the same number of processors. To attain full simulation scaling, we exploit an element agglomerated coarsening based on redistributing data to a reduced number of processors, which ensures both guaranteed coarse level accuracy and improves the solver scalability on coarse levels. The proposed redistribution utilizes only parallel sparse-matrix operations. This is completed during the AMG hierarchy construction to easily incorporate redistribution into multilevel MCMC. In this presentation, we will provide a high-level overview of our PDE-based random coefficient sampling approach used for multilevel MCMC, the newly developed redistribution method, and provide numerical examples to show improvements in coarse grid scaling.

ABSTRACT. The aim of this research is to develop efficient multigrid preconditioners for a classic linear-quadratic optimization problem constrained by an elliptic equation with stochastic coefficients. Using a discretize-then-optimize approach, in previous work we have shown that strategies inherited from the associated deterministic optimal control problem extend to the stochastic version when a stochastic Galerkin discretization is employed. In this talk we show that similar strategies succeed when discretizing the elliptic equation using a sparse grid stochastic collocation approach.