More Like this

1. Schur Complement Based Preconditioners for Twofold and Block Tridiagonal Saddle Point Problems

   https://doi.org/10.4208/cmr.2023-0051  

   Cai, Mingchao; Ju, Guoliang; Li, Jingzhi (May 2024, Communications in Mathematical Research)

   In this paper, we consider using Schur complements to design preconditioners for twofold and block tridiagonal saddle point problems. One type of the preconditioners are based on the nested (or recursive) Schur complement, the other is based on an additive type Schur complement after permuting the original saddle point systems. We analyze different preconditioners incorporating the exact Schur complements. We show that some of them will lead to positively stable preconditioned systems if proper signs are selected in front of the Schur complements. These positive-stable preconditioners outperform other preconditioners if the Schur complements are further approximated inexactly. Numerical experiments for a 3-field formulation of the Biot model are provided to verify our predictions. 

   more » « less
2. On the block Lanczos and block Golub–Kahan reduction methods applied to discrete ill‐posed problems

   https://doi.org/10.1002/nla.2376  

   Alqahtani, Abdulaziz; Gazzola, Silvia; Reichel, Lothar; Rodriguez, Giuseppe (March 2021, Numerical Linear Algebra with Applications)

   Abstract The reduction of a large‐scale symmetric linear discrete ill‐posed problem with multiple right‐hand sides to a smaller problem with a symmetric block tridiagonal matrix can easily be carried out by the application of a small number of steps of the symmetric block Lanczos method. We show that the subdiagonal blocks of the reduced problem converge to zero fairly rapidly with increasing block number. This quick convergence indicates that there is little advantage in expressing the solutions of discrete ill‐posed problems in terms of eigenvectors of the coefficient matrix when compared with using a basis of block Lanczos vectors, which are simpler and cheaper to compute. Similarly, for nonsymmetric linear discrete ill‐posed problems with multiple right‐hand sides, we show that the solution subspace defined by a few steps of the block Golub–Kahan bidiagonalization method usually can be applied instead of the solution subspace determined by the singular value decomposition of the coefficient matrix without significant, if any, reduction of the quality of the computed solution. 

   more » « less
3. Robust fast direct integral equation solver for three-dimensional doubly periodic scattering problems with a large number of layers

   https://doi.org/10.1016/j.jcp.2023.112573  

   Wu, Bowei; Cho, Min Hyung (December 2023, Journal of Computational Physics)

   Frequency-domain wave scattering problems that arise in acoustics and electromagnetism can be often described by the Helmholtz equation. This work presents a boundary integral equation method for the Helmholtz equation in 3-D multilayered media with many doubly periodic smooth layers. Compared with conventional quasi-periodic Green’s function method, the new method is robust at all scattering parameters. A periodizing scheme is used to decompose the solution into near-and far-field contributions. The near-field contribution uses the free-space Green’s function in an integral equation on the interface in the unit cell and its immediate eight neighbors; the far-field contribution uses proxy point sources that enclose the unit cell. A specialized high-order quadrature is developed to discretize the underlying surface integral operators to keep the number of unknowns per layer small. We achieve overall linear computational complexity in the number of layers by reducing the linear system into block tridiagonal form and then solving the system directly via block LU decomposition. The new solver is capable of handling a 100-interface structure with 961.3k unknowns to 10−5 accuracy in less than 2 hours on a desktop workstation. 

   more » « less
4. Optimization based data enrichment using stochastic dynamical system models

   https://doi.org/10.1371/journal.pone.0310504  

   Kearney, Griffin M; Fardad, Makan (September 2024, PLOS ONE)

   Zhang, Qichun (Ed.)

   We develop a general framework for state estimation in systems modeled with noise-polluted continuous time dynamics and discrete time noisy measurements. Our approach is based on maximum likelihood estimation and employs the calculus of variations to derive optimality conditions for continuous time functions. We make no prior assumptions on the form of the mapping from measurements to state-estimate or on the distributions of the noise terms, making the framework more general than Kalman filtering/smoothing where this mapping is assumed to be linear and the noises Gaussian. The optimal solution that arises is interpreted as a continuous time spline, the structure and temporal dependency of which is determined by the system dynamics and the distributions of the process and measurement noise. Similar to Kalman smoothing, the optimal spline yields increased data accuracy at instants when measurements are taken, in addition to providing continuous time estimates outside the measurement instances. We demonstrate the utility and generality of our approach via illustrative examples that render both linear and nonlinear data filters depending on the particular system. Application of the proposed approach to a Monte Carlo simulation exhibits significant performance improvement in comparison to a common existing method. 

   more » « less
5. Analysis of EDF for Real-Time Multiprocessor Systems with Resource Sharing

   https://doi.org/10.4230/lipics.ecrts.2025.15  

   Agrawal, Kunal; Baruah, Sanjoy; Fineman, Jeremy T; Marchetti-Spaccamela, Alberto; Zhao, Jinhao (July 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mancuso, Renato (Ed.)

   The classic Earliest Deadline First (EDF) algorithm is widely studied and used due to its simplicity and strong theoretical performance, but has not been rigorously analyzed for systems where jobs may execute critical sections protected by shared locks. Analyzing such systems is often challenging due to unpredictable delays caused by contention. In this paper, we propose a straightforward generalization of EDF, called EDF-Block. In this generalization, the critical sections are executed non-preemptively, but scheduling and lock acquisition priorities are based on EDF. We establish lower bounds on the speed augmentation required for any non-clairvoyant scheduler (EDF-Block is an example of non-clairvoyant schedulers) and for EDF-Block, showing that EDF-Block requires at least 4.11× speed augmentation for jobs and 4× for tasks. We then provide an upper bound analysis, demonstrating that EDF-Block requires speedup of at most 6 to schedule all feasible job and task sets. 

   more » « less