skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Probabilistic Condition Number Estimates for Real Polynomial Systems I: A Broader Family of Distributions
We consider the sensitivity of real roots of polynomial systems with respect to perturbations of the coefficients. In particular --- for a version of the condition number defined by Cucker and used later by Cucker, Krick, Malajovich, and Wschebor --- we establish new probabilistic estimates that allow a much broader family of measures than considered earlier. We also generalize further by allowing over-determined systems. In Part II, we study smoothed complexity and how sparsity (in the sense of restricting which terms can appear) can help further improve earlier condition number estimates.  more » « less
Award ID(s):
1409020
PAR ID:
10074766
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Foundations of Computational Mathematics
ISSN:
1615-3375
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, 3th International Conference on Applications of Statistics and Probability in Civil Engineering, ICASP13)
    Risk assessment of power transmission systems against strong winds requires models that can accurately represent the realistic performance of the physical infrastructure. Capturing material nonlinearity, p-delta effects in towers, buckling of lattice elements, joint slippage, and joint failure requires nonlinear models. For this purpose, this study investigates the reliability of transmission line systems by utilizing a nonlinear model of steel lattice towers, generated in OpenSEES platform. This model is capable of considering various geometric and material nonlinearities mentioned earlier. In order to efficiently estimate the probability of failure of transmission lines, the current study adopts an advanced reliability method through Error rate-based Adaptive Kriging (REAK) proposed by the authors. This method is capable of significantly reducing the number of simulations compared to conventional Monte Carlo methods such that reliability analysis can be done within a reasonable time. Results indicate that REAK efficiently estimates the reliability of transmission lines with a maximum of 150 Finite Element simulations for various wind intensities. 
    more » « less
  2. ; ; (, Mathematics of Computation)
    We consider the sensitivity of real zeros of structured polynomial systems to pertubations of their coefficients. In particular, we provide explicit estimates for condition numbers of structured random real polynomial systems and extend these estimates to the smoothed analysis setting. 
    more » « less
  3. ; (, 2021 IEEE International Conference on Robotics and Automation (ICRA),)
    This paper addresses the long-standing open problem of observability of mass and inertia plant parameters in the adaptive identification (AID) of second-order nonlinear models of 6 degree-of-freedom rigid-body dynamical systems subject to externally applied forces and moments. Although stable methods for AID of plant parameters for this class of systems, as well numerous approaches to stable model-based direct adaptive trajectory-tracking control of such systems, have been reported, these studies have been unable to prove analytically that the adaptive parameter estimates converge to the true plant parameter values. This paper reports necessary and sufficient conditions for the uniform complete observability (UCO) of 6-DOF plant inertial parameters for a stable adaptive identifier for this class of systems. When the UCO condition is satisfied, the adaptive parameter estimates are shown to converge to the true plant parameter values. To the best of our knowledge this is the first reported proof for this class of systems of UCO of plant parameters and for convergence of adaptive parameter estimates to true parameter values.We also report a numerical simulation study of this AID approach which shows that (a) the UCO condition can be met for fully-actuated plants as well as underactuated plants with the proper choice of control input and (b) convergence of adaptive parameter estimates to the true parameter values. We conjecture that this approach can be extended to include other parameters that appear rigid body plant models including parameters for drag, buoyancy, added mass, bias, and actuators. 
    more » « less
  4. ; ; (, Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control)
    null (Ed.)
    In this paper, we present a compositional condition for ensuring safety of a collection of interacting systems modeled by inter-triggering hybrid automata (ITHA). ITHA is a modeling formalism for representing multi-agent systems in which each agent is governed by individual dynamics but can also interact with other agents through triggering actions. These triggering actions result in a jump/reset in the state of other agents according to a global resolution function. A sufficient condition for safety of the collection, inspired by responsibility-sensitive safety, is developed in two parts: self-safety relating to the individual dynamics, and responsibility relating to the triggering actions. The condition relies on having an over-approximation method for the resolution function. We further show how such over-approximations can be obtained and improved via communication. We use two examples, a job scheduling task on parallel processors and a highway driving example, throughout the paper to illustrate the concepts. Finally, we provide a comprehensive evaluation on how the proposed condition can be leveraged for several multi-agent control and supervision examples. 
    more » « less
  5. ; ; (, Proceedings of the ACM on Measurement and Analysis of Computing Systems)
    null (Ed.)
    Applications in cloud platforms motivate the study of efficient load balancing under job-server constraints and server heterogeneity. In this paper, we study load balancing on a bipartite graph where left nodes correspond to job types and right nodes correspond to servers, with each edge indicating that a job type can be served by a server. Thus edges represent locality constraints, i.e., an arbitrary job can only be served at servers which contain certain data and/or machine learning (ML) models. Servers in this system can have heterogeneous service rates. In this setting, we investigate the performance of two policies named Join-the-Fastest-of-the-Shortest-Queue (JFSQ) and Join-the-Fastest-of-the-Idle-Queue (JFIQ), which are simple variants of Join-the-Shortest-Queue and Join-the-Idle-Queue, where ties are broken in favor of the fastest servers. Under a "well-connected'' graph condition, we show that JFSQ and JFIQ are asymptotically optimal in the mean response time when the number of servers goes to infinity. In addition to asymptotic optimality, we also obtain upper bounds on the mean response time for finite-size systems. We further show that the well-connectedness condition can be satisfied by a random bipartite graph construction with relatively sparse connectivity. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email