More Like this

1. Uncertainty in Boundary Conditions---An Interval Finite Element Approach

   https://doi.org/10.1007/978-3-030-40814-5_20  

   Muhanna, Rafi; Shahi, Shahrokh (January 2020, Decision Making under Constraints)

   In this work, we introduce an interval formulation that accounts for uncertainty in supporting conditions of structural systems. Uncertainty in structural systems has been the focus of a wide range of research. Different models of uncertain parameters have been used. Conventional treatment of uncertainty involves probability theory, in which uncertain parameters are modeled as random variables. Due to specific limitation of probabilistic approaches, such as the need of a prior knowledge on the distributions, lack of complete information, and in addition to their intensive computational cost, the rationale behind their results is under debate. Alternative approaches such as fuzzy sets, evidence theory, and intervals have been developed. In this work, it is assumed that only bounds on uncertain parameters are available and intervals are used to model uncertainty. Here, we present a new approach to treat uncertainty in supporting conditions. Within the context of Interval Finite Element Method (IFEM), all uncertain parameters are modeled as intervals. However, supporting conditions are considered in idealized types and described by deterministic values without accounting for any form of uncertainty. In the current developed approach, uncertainty in supporting conditions is modeled as bounded range of values, i.e., interval value that capture any possible variation in supporting condition within a given interval. Extreme interval bounds can be obtained by analyzing the considered system under the conditions of the presence and absence of the specific supporting condition. A set of numerical examples is presented to illustrate and verify the accuracy of the proposed approach. 

   more » « less
2. Efficient algorithms for dynamic bidirected Dyck-reachability

   https://doi.org/10.1145/3498724  

   Li, Yuanbo; Satya, Kris; Zhang, Qirun (January 2022, Proceedings of the ACM on Programming Languages)

   Dyck-reachability is a fundamental formulation for program analysis, which has been widely used to capture properly-matched-parenthesis program properties such as function calls/returns and field writes/reads. Bidirected Dyck-reachability is a relaxation of Dyck-reachability on bidirected graphs where each edge u → ( i v labeled by an open parenthesis “( i ” is accompanied with an inverse edge v → ) i u labeled by the corresponding close parenthesis “) i ”, and vice versa. In practice, many client analyses such as alias analysis adopt the bidirected Dyck-reachability formulation. Bidirected Dyck-reachability admits an optimal reachability algorithm. Specifically, given a graph with n nodes and m edges, the optimal bidirected Dyck-reachability algorithm computes all-pairs reachability information in O ( m ) time. This paper focuses on the dynamic version of bidirected Dyck-reachability. In particular, we consider the problem of maintaining all-pairs Dyck-reachability information in bidirected graphs under a sequence of edge insertions and deletions. Dynamic bidirected Dyck-reachability can formulate many program analysis problems in the presence of code changes. Unfortunately, solving dynamic graph reachability problems is challenging. For example, even for maintaining transitive closure, the fastest deterministic dynamic algorithm requires O ( n 2 ) update time to achieve O (1) query time. All-pairs Dyck-reachability is a generalization of transitive closure. Despite extensive research on incremental computation, there is no algorithmic development on dynamic graph algorithms for program analysis with worst-case guarantees. Our work fills the gap and proposes the first dynamic algorithm for Dyck reachability on bidirected graphs. Our dynamic algorithms can handle each graph update ( i.e. , edge insertion and deletion) in O ( n ·α( n )) time and support any all-pairs reachability query in O (1) time, where α( n ) is the inverse Ackermann function. We have implemented and evaluated our dynamic algorithm on an alias analysis and a context-sensitive data-dependence analysis for Java. We compare our dynamic algorithms against a straightforward approach based on the O ( m )-time optimal bidirected Dyck-reachability algorithm and a recent incremental Datalog solver. Experimental results show that our algorithm achieves orders of magnitude speedup over both approaches. 

   more » « less
3. An iterative decoupled algorithm with unconditional stability for Biot model

   https://doi.org/10.1090/mcom/3809  

   Gu, Huipeng; Cai, Mingchao; Li, Jingzhi (May 2023, Mathematics of Computation)

   This paper is concerned with numerical algorithms for Biot model. By introducing an intermediate variable, the classical 2-field Biot model is written into a 3-field formulation. Based on such a 3-field formulation, we propose a coupled algorithm, some time-extrapolation based decoupled algorithms, and an iterative decoupled algorithm. Our focus is the analysis of the iterative decoupled algorithm. It is shown that the convergence of the iterative decoupled algorithm requires no extra assumptions on physical parameters or stabilization parameters. Numerical experiments are provided to demonstrate the accuracy and efficiency of the proposed method. 

   more » « less
4. An Iterative Decoupled Algorithm with Unconditional Stability for Biot Model

   Gu H., Cai M. (May 2023, Mathematics of computation)

   This paper is concerned with numerical algorithms for Biot model. By introducing an intermediate variable, the classical 2-field Biot model is written into a 3-field formulation. Based on such a 3-field formulation, we propose a coupled algorithm, some time-extrapolation based decoupled algorithms, and an iterative decoupled algorithm. Our focus is the analysis of the iterative decoupled algorithm. It is shown that the convergence of the iterative decoupled algorithm requires no extra assumptions on physical parameters or stabilization parameters. Numerical experiments are provided to demonstrate the accuracy and efficiency of the proposed method. 

   more » « less
5. Direct/Iterative Hybrid Solver for Scattering by Inhomogeneous Media

   https://doi.org/10.1137/22M1521547  

   Bruno, Oscar P; Pandey, Ambuj (April 2024, SIAM Journal on Scientific Computing)

   Bruno, Oscar; Pandey, Ambuj (Ed.)

   This paper presents a fast high-order method for the solution of two-dimensional problems of scattering by penetrable inhomogeneous media, with application to high-frequency configurations containing (possibly) discontinuous refractivities. The method relies on a hybrid direct/iterative combination of 1)~A differential volumetric formulation (which is based on the use of appropriate Chebyshev differentiation matrices enacting the Laplace operator) and, 2)~A second-kind boundary integral formulation (which, once again, utilizes Chebyshev discretization, but, in this case, in the boundary-integral context). The approach enjoys low dispersion and high-order accuracy for smooth refractivities, as well as second-order accuracy (while maintaining low dispersion) in the discontinuous refractivity case. The solution approach proceeds by application of Impedance-to-Impedance (ItI) maps to couple the volumetric and boundary discretizations. The volumetric linear algebra solutions are obtained by means of a multifrontal solver, and the coupling with the boundary integral formulation is achieved via an application of the iterative linear-algebra solver GMRES. In particular, the existence and uniqueness theory presented in the present paper provides an affirmative answer to an open question concerning the existence of a uniquely solvable second-kind ItI-based formulation for the overall scattering problem under consideration. Relying on a modestly-demanding scatterer-dependent precomputation stage (requiring in practice a computing cost of the order of $$O(N^{\alpha})$$ operations, with $$\alpha \approx 1.07$$, for an $$N$$-point discretization \textcolor{black}{and for the relevant Chebyshev accuracy orders $$q$$ used)}, together with fast ($O(N)$-cost) single-core runs for each incident field considered, the proposed algorithm can effectively solve scattering problems for large and complex objects possibly containing discontinuities and strong refractivity contrasts. 

   more » « less