More Like this

1. Transient Adjoint DAE Sensitivities: a Complete, Rigorous, and Numerically Accurate Formulation

   https://doi.org/10.1109/ASP-DAC52403.2022.9712537  

   Sagan, Naomi; Roychowdhury, Jaijeet (January 2022, 2022 27th Asia and South Pacific Design Automation Conference (ASP-DAC))

   Almost all practical systems rely heavily on physical parameters. As a result, parameter sensitivity, or the extent to which perturbations in parameter values affect the state of a system, is intrinsically connected to system design and optimization. We present TADsens, a method for computing the parameter sensitivities of an output of a differential algebraic equation (DAE) system. Specifically, we provide rigorous, insightful theory for adjoint sensitivity computation of DAEs, along with an efficient and numerically well-posed algorithm implemented in Berkeley MAPP. Our theory and implementation advances resolve longstanding issues that have impeded adoption of adjoint transient sensitivities in circuit simulators for over 5 decades. We present results and comparisons on two nonlinear analog circuits. TADsens is numerically well posed and accurate, and faster by a factor of 300 over direct sensitivity computation on a circuit with over 150 unknowns and 600 parameters. 

   more » « less
2. Algorithms yield upper bounds in differential algebra

   https://doi.org/10.4153/S0008414X21000560  

   Li, Wei; Ovchinnikov, Alexey; Pogudin, Gleb; Scanlon, Thomas (September 2021, Canadian Journal of Mathematics)

   Consider an algorithm computing in a differential field with several commuting derivations such that the only operations it performs with the elements of the field are arithmetic operations, differentiation, and zero testing. We show that, if the algorithm is guaranteed to terminate on every input, then there is a computable upper bound for the size of the output of the algorithm in terms of the size of the input. We also generalize this to algorithms working with models of good enough theories (including, for example, difference fields). We then apply this to differential algebraic geometry to show that there exists a computable uniform upper bound for the number of components of any variety defined by a system of polynomial PDEs. We then use this bound to show the existence of a computable uniform upper bound for the elimination problem in systems of polynomial PDEs with delays. 

   more » « less
3. Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints

   Qiao, Dan; Wang, Yu-Xiang (July 2024, Proceedings of Machine Learning Research)

   We study the problem of multi-agent reinforcement learning (MARL) with adaptivity constraints -- a new problem motivated by real-world applications where deployments of new policies are costly and the number of policy updates must be minimized. For two-player zero-sum Markov Games, we design a (policy) elimination based algorithm that achieves a regret of O˜(H3S2ABK‾‾‾‾‾‾‾‾‾‾√), while the batch complexity is only O(H+loglogK). In the above, S denotes the number of states, A,B are the number of actions for the two players respectively, H is the horizon and K is the number of episodes. Furthermore, we prove a batch complexity lower bound Ω(HlogAK+loglogK) for all algorithms with O˜(K‾‾√) regret bound, which matches our upper bound up to logarithmic factors. As a byproduct, our techniques naturally extend to learning bandit games and reward-free MARL within near optimal batch complexity. To the best of our knowledge, these are the first line of results towards understanding MARL with low adaptivity. 

   more » « less
4. On the Use of Half-Implicit Numerical Integration in Multibody Dynamics

   https://doi.org/10.1115/1.4056183  

   Fang, Luning; Kissel, Alexandra; Zhang, Ruochun; Negrut, Dan (January 2023, Journal of Computational and Nonlinear Dynamics)

   Abstract This work highlights the use of half-implicit numerical integration in the context of the index three differential algebraic equations (DAEs) of multibody dynamics. Although half-implicit numerical integration is well established for ordinary differential equations problems, to the best of our knowledge, no formal discussion covers its use in the context of index three DAEs of multibody dynamics. We wish to address this since when compared to fully implicit methods, half-implicit integration has two attractive features: (i) the solution method does not require the computation of the Jacobian associated with the constraint, friction, contact, or user-defined applied forces; and (ii) the solution is simpler to implement. Moreover, for nonstiff problems, half-implicit numerical integration yields a faster solution. Herein, we outline the numerical method and demonstrate it in conjunction with three mechanisms. We report on convergence order behavior and solution speed. The Python software developed to generate the results reported is available as open in a public repository for reproducibility studies. 

   more » « less
5. On the number of Hadamard matrices via anti-concentration

   https://doi.org/10.1017/S0963548321000377  

   Ferber, Asaf; Jain, Vishesh; Zhao, Yufei (May 2022, Combinatorics, Probability and Computing)

   Abstract Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations $Ax = b$ , where the coordinates of the vector x are restricted to take values in some small subset (e.g. $$\{\pm 1\}$$ ) of the underlying field. The classical ways of bounding this quantity are to use either a rank bound observation due to Odlyzko or a vector anti-concentration inequality due to Halász. The former gives a stronger conclusion except when the number of equations is significantly smaller than the number of variables; even in such situations, the hypotheses of Halász’s inequality are quite hard to verify in practice. In this paper, using a novel approach to the anti-concentration problem for vector sums, we obtain new Halász-type inequalities that beat the Odlyzko bound even in settings where the number of equations is comparable to the number of variables. In addition to being stronger, our inequalities have hypotheses that are considerably easier to verify. We present two applications of our inequalities to combinatorial (random) matrix theory: (i) we obtain the first non-trivial upper bound on the number of $$n\times n$$ Hadamard matrices and (ii) we improve a recent bound of Deneanu and Vu on the probability of normality of a random $$\{\pm 1\}$$ matrix. 

   more » « less