Search

Summary: Large‐scale linear time‐invariant (LTI) dynamical systems are widely used to characterize complicated physical phenomena. Glover developed the Hankel norm approximation (HNA) algorithm for optimally reducing the system in the Hankel norm, and we study its numerical issues. We provide a remedy for the numerical instabilities of Glover's HNA algorithm caused by clustered singular values. We analyze the effect of our modification on the degree and the Hankel error of the reduced system. Moreover, we propose a two‐stage framework to reduce the order of a large‐scale LTI system given samples of its transfer function for a target degree k$$ k $$ of the reduced system. It combines the adaptive Antoulas–Anderson (AAA) algorithm, modified to produce an intermediate LTI system in a numerically stable way, and the modified HNA algorithm. A carefully computed rational approximation of an adaptively chosen degree d$$ d $$ gives us an algorithm for reducing an LTI system, which achieves a balance between speed and accuracy. [ABSTRACT FROM AUTHOR]

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real‐valued functions f:{0,1}d→ℝ$$ f:{\left\{0,1\right\}}^d\to \mathbb{R} $$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real‐valued function f$$ f $$ over an arbitrary partially ordered domain as a collection of Boolean functions over the same domain, roughly capturing the distance of f$$ f $$ to monotonicity and the structure of violations of f$$ f $$ to monotonicity. We apply our generalized isoperimetric inequality to improve algorithms for testing monotonicity and approximating the distance to monotonicity for real‐valued functions. Our tester for monotonicity has query complexity O˜(min(rd,d))$$ \tilde{O}\left(\min \left(r\sqrt{d},d\right)\right) $$, where r$$ r $$ is the size of the image of the input function. (The best previously known tester makes O(d)$$ O(d) $$ queries, as shown by Chakrabarty and Seshadhri (STOC 2013).) Our tester is nonadaptive and has 1‐sided error. We prove a matching lower bound for nonadaptive, 1‐sided error testers for monotonicity. We also show that the distance to monotonicity of real‐valued functions that are α$$ \alpha $$‐far from monotone can be approximated nonadaptively within a factor of O(dlogd)$$ O\left(\sqrt{d\log d}\right) $$ with query complexity polynomial in 1/α$$ 1/\alpha $$ and the dimension d$$ d $$. This query complexity is nearly optimal for nonadaptive algorithms even for the special case of Boolean functions (The best previously known distance approximation algorithm for real‐valued functions, by Fattal and Ron (TALG 2010) achieves O(dlogr)$$ O\left(d\log r\right) $$‐approximation.). [ABSTRACT FROM AUTHOR]

In topology optimization of transient problems, memory requirements and computational costs often become prohibitively large due to the backward‐in‐time adjoint equations. Common approaches such as the Checkpointing (CP) and Local‐in‐Time (LT) algorithms reduce memory requirements by dividing the temporal domain into intervals and by computing sensitivities on one interval at a time. The CP algorithm reduces memory by recomputing state solutions instead of storing them. This leads to a significant increase in computational cost. The LT algorithm introduces approximations in the adjoint solution to reduce memory requirements and leads to a minimal increase in computational effort. However, we show that convergence can be hampered using the LT algorithm due to errors in approximate adjoints. To reduce memory and/or computational time, we present two novel algorithms. The hybrid Checkpointing/Local‐in‐Time (CP/LT) algorithm improves the convergence behavior of the LT algorithm at the cost of an increased computational time but remains more efficient than the CP algorithm. The Parallel‐Local‐in‐Time (PLT) algorithm reduces the computational time through a temporal parallelization in which state and adjoint equations are solved simultaneously on multiple intervals. State and adjoint fields converge concurrently with the design. The effectiveness of each approach is illustrated with two‐dimensional density‐based topology optimization problems involving transient thermal or flow physics. Compared to the other discussed algorithms, we found a significant decrease in computational time for the PLT algorithm. Moreover, we show that under certain conditions, due to the use of approximations in the LT and PLT algorithms, they exhibit a bias toward designs with short characteristic times. Finally, based on the required memory reduction, computational cost, and convergence behavior of optimization problems, guidelines are provided for selecting the appropriate algorithms. [ABSTRACT FROM AUTHOR]

Reactive silica materials like vitreous silica or cristobalite were dissolved at temperatures between 100 and 220 °C for up to 7 days in NaOH lyes. The liquid and solid reaction products were analyzed chemically. Sodium water glasses with silica concentrations of up to 27 wt % and molar SiO2/Na2O ratios of up to 3.7 were obtained. The experimental data were evaluated by an approximation algorithm. The initial size reduction rates ranged between 0.1 and 7 µm h−1, depending on the temperature and the choice of starting materials. Correlations between thermodynamics and kinetics were discussed. [ABSTRACT FROM AUTHOR]

This article focuses on designing efficient iteration algorithms for nonequilibrium three‐temperature heat conduction equations, which are used to formulate the radiative energy transport problem. Based on the framework of relaxation iteration, we design a new accelerated iteration algorithm by reasonable approximation of the Jacobi matrix, according to the characteristics of the discrete scheme for the three‐temperature equations. Adopting the iteration framework, we analyze the advantages and disadvantages of several iteration algorithms commonly used in practice and the new iteration algorithm. Finally, we compare the new iteration algorithm with some other iteration algorithms by solving several nonlinear models, and show that the new algorithm can achieve significant acceleration effect. [ABSTRACT FROM AUTHOR]

Objective: Elective‐emergency admission control referred to allocating available inpatient bed capacity between elective and emergency hospitalization demand. Existing approaches for admission control often excluded several complex factors when making decisions, such as uncertain bed capacity and unknown true probability distributions of patient arrivals and departures. We aimed to create a data‐driven newsvendor framework to study the elective‐emergency admission control problem to achieve bed operational efficiency and effectiveness. Methods: We developed a data‐driven approach that utilized the newsvendor framework to formulate the admission control problem. We also created approximation algorithms to generate a pool of candidate admission control solutions. Past observations and relevant emergency demand and bed capacity features were modeled in a newsvendor framework. Using approximation algorithmic approaches (sample average approximation, separated estimation and optimization, linear programing‐LP, and distribution‐free model) allowed us to derive computationally efficient data‐driven solutions with tight bounds on the expected in‐sample and out‐of‐sample cost guaranteed. Results: Tight generalization bounds on the expected out‐of‐sample cost of the feature‐based model were derived with respect to the LP and quadratic programing (QP) algorithms, respectively. Results showed that the optimal feature‐based model outperformed the optimal observation‐based model with respect to the expected cost. In a setting where the unit overscheduled cost was higher than the unit under‐scheduled cost, scheduling fewer elective patients would replace the benefit of incorporating related features in the model. The tighter the available bed capacity for elective patients, the bigger the difference of the schedule cost between the feature‐based model and the observation‐based model. Conclusions: The study provides a reference for the theoretical study on bed capacity allocation between elective and emergency patients under the condition of the unknown true probability distribution of bed capacity and emergency demand, and it also proves that the approximate optimal policy has good performance. [ABSTRACT FROM AUTHOR]

In this article, we consider the rank‐structured approximation of one important type of Cauchy matrix. This approximation plays a key role in some structured matrix methods such as stable and efficient direct solvers and other algorithms for Toeplitz matrices and certain kernel matrices. Previous rank‐structured approximations (specifically hierarchically semiseparable, or HSS, approximations) for such a matrix of size n$$ n $$ cost at least O(n)$$ O(n) $$ complexity. Here, we show how to construct an HSS approximation with sublinear (specifically, O(log3n)$$ O\left({\log}^3n\right) $$) complexity. The main ideas include extensive computation reuse and an analytical far‐field compression strategy. Low‐rank compression at each hierarchical level is restricted to just a single off‐diagonal block row, and a resulting basis matrix is then reused for other off‐diagonal block rows as well as off‐diagonal block columns. The relationships among the off‐diagonal blocks are rigorously analyzed. The far‐field compression uses an analytical proxy point method where we optimize the choice of some parameters so as to obtain accurate low‐rank approximations. Both the basis reuse ideas and the resulting analytical hierarchical compression scheme can be generalized to some other kernel matrices and are useful for accelerating relevant rank‐structured approximations (though not subsequent operations like matrix‐vector multiplications). [ABSTRACT FROM AUTHOR]

The design of distribution networks that simultaneously consider location and inventory decisions seeks to balance costs and product availability. The most commonly observed measure of product availability in practical settings is the fill‐rate service level. However, the optimal design of a distribution network that considers the fill rate to control shortages of fast‐moving consumer goods (FMCG) is considered intractable and has only been addressed by heuristic methods. This paper addresses the optimal design of a distribution network for FMCG able to provide high fill‐rate service level under a continuous review (r,Q)$(r,Q)$ policy. Considering the exact formulation for the provided fill rate, we formulated a joint location–inventory model with fill‐rate service level constraints as a convex mixed integer nonlinear problem for which a novel decomposition‐based outer approximation algorithm is proposed. Numerical experiments have shown that our solution approach provides good‐quality solutions that are on average 0.15% and, at worst, 2.2% from the optimal solution. [ABSTRACT FROM AUTHOR]