Search

This is the second paper in a series of two. The goal of the series is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial time-algorithm that starts with a 4-precoloring of a graph with no induced six-vertex path and outputs a polynomial-sized collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem. [ABSTRACT FROM AUTHOR]

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ϵ>0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an ϵ expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ϵ-kernels of point sets, approximate nearest neighbor searching, polytope approximations, and approximations to the Closest Vector Problem (CVP). It is known how to construct coverings of size nO(n)/ϵ(n-1)/2 for general convex bodies in Rn. In special cases, such as when the convex body is the ℓp unit ball, this bound has been improved to 2O(n)/ϵ(n-1)/2. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, under the Banach-Mazur metric. Given a well-centered convex body K and an approximation parameter ϵ>0, we show that there exists a polytope P consisting of 2O(n)/ϵ(n-1)/2 vertices (facets) such that K⊂P⊂K(1+ϵ). This bound is optimal in the worst case up to factors of 2O(n). As an additional consequence, we obtain the fastest (1+ϵ)-approximate CVP algorithm that works in any norm, with a running time of 2O(n)/ϵ(n-1)/2 up to polynomial factors in the input size, and we obtain the fastest (1+ϵ)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of 2O(n)). [ABSTRACT FROM AUTHOR]

This paper derives a discrete dual problem for a prototypical hybrid high-order method for convex minimization problems. The discrete primal and dual problem satisfy a weak convex duality that leads to a priori error estimates with convergence rates under additional smoothness assumptions. This duality holds for general polyhedral meshes and arbitrary polynomial degrees of the discretization. A novel postprocessing is proposed and allows for a posteriori error estimates on regular triangulations into simplices using primal-dual techniques. This motivates an adaptive mesh-refining algorithm, which performs better compared to uniform mesh refinements. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a hybridizable discontinuous Galerkin method for the Helmholtz equation with large wave number, which uses piecewise polynomials of degree of p ≥ 1 to approximate the potential u and its traces and piecewise polynomials of degree of p - 1 for the flux q. It is proved that ... and ... hold under the conditions that k(kh)2p is sufficiently small and that the penalty parameter ..., where h is the mesh size. Numerical experiments are proposed to verify our theoretical findings and to show that the pollution error may be greatly reduced by tuning the penalty parameter. [ABSTRACT FROM AUTHOR]

Stochastic rounding (SR) offers an alternative to the deterministic IEEE-754 floating-point rounding modes. In some applications such as PDEs, ODEs, and neural networks, SR empirically improves the numerical behavior and convergence to accurate solutions while the theoretical background remains partial. Recent works by Ipsen, Zhou, Higham, and Mary have computed SR probabilistic error bounds for basic linear algebra kernels. For example, the inner product SR probabilistic bound of the forward error is proportional to √nu instead of nu for the default rounding mode. To compute the bounds, these works show that the errors accumulated in computation form a martingale. This paper proposes an alternative framework to characterize SR errors based on the computation of the variance. We pinpoint common error patterns in numerical algorithms and propose a lemma that bounds their variance. For each probability and through the Bienaymé-Chebyshev inequality, this bound leads to a better probabilistic error bound in several situations. Our method has the advantage of providing a tight probabilistic bound for all algorithms fitting our model. We show how the method can be applied to give SR error bounds for the inner product and Horner polynomial evaluation. [ABSTRACT FROM AUTHOR]

The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp. 151-160] is a general way to prove lower bounds on the hereditary discrepancy of a set system. In their paper, Lovász, Spencer, and Vesztergombi asked if hereditary discrepancy can also be bounded from above by a function of the determinant lower bound. This was answered in the negative by Hoffman, and the largest known multiplicative gap between the two quantities for a set system of m subsets of a universe of size n is on the order of max {log n, √log m}. On the other hand, building upon work of Matousek [Proc. Amer. Math. Soc., 141 (2013), pp. 451-460], Jiang and Reis [in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, 2022, pp. 308-313] showed that this gap is always bounded up to constants by √log(m)log(n). This is tight when m is polynomial in n but leaves open the case of large m. We show that the bound of Jiang and Reis is tight for nearly the entire range of m. Our proof amplifies the discrepancy lower bounds of a set system derived from the discrete Haar basis via Kronecker products. [ABSTRACT FROM AUTHOR]

In this paper, we strengthen a result by Green about an analogue of Sárközy's theorem in the setting of polynomial rings Fq[x]. In the integer setting, for a given polynomial F ∈ Z[x] with constant term zero, (a generalization of) Sárközy's theorem gives an upper bound on the maximum size of a subset A ⊂{1, ..., n} that does not contain distinct α1, α2 ∈ A satisfying α1, -- α2 = F(b) for some b ∈ Z. Green proved an analogous result with much stronger bounds in the setting of subsets A ⊂ Fq[x] of the polynomial ring Fq[x], but this result required the additional condition that the number of roots of the polynomial F ∈ Fq[x] be coprime to q. We generalize Green's result, removing this condition. As an application, we also obtain a version of Sárközy's theorem with similar strong bounds for subsets A ⊂ Fq for q=pn for a fixed prime p and large n. [ABSTRACT FROM AUTHOR]

A nonnegativity certificate (NNC) is a way to write a polynomial so that its nonnegativity on a Semialgebraic set becomes evident. Positivstellensatze (Psatze) guarantee the existence of NNCs. Both NNCs and Psatze underlie powerful algorithmic techniques for optimization. This paper proposes a universal approach to derive new Psatze for general Semialgebraic sets from ones developed for simpler sets, such as a box, a simplex, or the nonnegative orthant. We provide several results illustrating the approach. First, by considering Handelman's Positivstellensatz (Psatz) over a box, we construct non-SOS Schmüdgen-type Psatze over any compact Semialgebraic set, that is, a family of Psatze that follow the structure of the fundamental Schmiidgen's Psatz but where instead of SOS polynomials, any class of polynomials containing the nonnegative constants can be used, such as SONC, DSOS/SDSOS, hyperbolic, or sums of AM/GM polynomials. Second, by considering the simplex as the simple set, we derive a sparse Psatz over general compact sets which does not rely on any structural assumptions of the set. Finally, by considering Polya's Psatz over the nonnegative orthant, we derive a new non-SOS Psatz over unbounded sets which satisfy some generic conditions. All these results contribute to the literature regarding the use of non-SOS polynomials and sparse NNCs to derive Psatze over compact and unbounded sets. Throughout the article, we illustrate our results with relevant examples and numerical experiments. [ABSTRACT FROM AUTHOR]

Bell inequalities are pillars of quantum physics in that their violations imply that certain properties of quantum physics (e.g., entanglement) cannot be represented by any classical picture of physics. In this article Bell inequalities and their violations are considered through the lens of noncommutative polynomial optimization. Optimality of these violations is certified for a large ma jority of a set of standard Bell inequalities, denoted A2--A89 in the literature. The main techniques used in the paper include the NPA hierarchy, i.e., the noncommutative version of the Lasserre semidefinite programming (SDP) hierarchies based on the Helton--McCullough Positivstellensatz, the Gelfand--Naimark--Segal (GNS) construction with a novel use of the Artin--Wedderburn theory for rounding and projecting, and nonlinear programming (NLP). A new "Newton chip""-like technique for reducing sizes of SDPs arising in the constructed polynomial optimization problems is presented. This technique is based on conditional expectations. Finally, noncommutative Grobner bases are exploited to certify when an optimizer (a solution yielding optimum violation) cannot be extracted from a dual SDP solution. [ABSTRACT FROM AUTHOR]

In this paper, we study the stabilization issue for a multidimensional wave equation with localized Kelvin--Voigt damping on a cuboidal domain, in which the damping region does not satisfy the geometric control condition (GCC). The variable damping coefficient is assumed to be degenerate near the interface. We prove that the system is polynomially stable with a decay rate depending on the degree of the degeneration γ. A relationship between the decay order and γ is identified. In particular, this decay rate is consistent with the optimal one for the corresponding system with constant damping coefficient (i.e., γ = 0) obtained in [K. Yu and Z.-J. Han, SIAM J. Control Optim., 59 (2021), pp. 1973--1988]. Moreover, it is the first result on the decay rates of the solutions to multidimensional wave equations with localized degenerate Kelvin--Voigt damping when GCC is not satisfied. [ABSTRACT FROM AUTHOR]

In this paper, we consider polynomial optimization with correlative sparsity. We construct correlatively sparse Lagrange multiplier expressions (CS-LMEs) and propose CS-LME reformulations for polynomial optimization problems using the Karush-Kuhn-Tucker optimality conditions. Correlatively sparse sum-of-squares (CS-SOS) relaxations are applied to solve the CS-LME reformulation. We show that the CS-LME reformulation inherits the original correlative sparsity pattern, and the CS-SOS relaxation provides sharper lower bounds when applied to the CS-LME reformulation, compared with when it is applied to the original problem. Moreover, the convergence of our approach is guaranteed under mild conditions. In numerical experiments, our new approach usually finds the global optimal value (up to a negligible error) with a low relaxation order for cases where directly solving the problem fails to get an accurate approximation. Also, by properly exploiting the correlative sparsity, our CS-LME approach requires less computational time than the original LME approach to reach the same accuracy level. [ABSTRACT FROM AUTHOR]

Runge--Kutta (RK) methods may exhibit order reduction when applied to stiff problems. For linear problems with time-independent operators, order reduction can be avoided if the method satisfies certain weak stage order (WSO) conditions, which are less restrictive than traditional stage order conditions. This paper outlines the first algebraic theory of WSO, and establishes general order barriers that relate the WSO of a RK scheme to its order and number of stages for both fully-implicit and DIRK schemes. It is shown in several scenarios that the constructed bounds are sharp. The theory characterizes WSO in terms of orthogonal invariant subspaces and associated minimal polynomials. The resulting necessary conditions on the structure of RK methods with WSO are then shown to be of practical use for the construction of such schemes. [ABSTRACT FROM AUTHOR]

In this paper, we consider the tensor absolute value equations (TAVEs). When one tensor is row diagonal with odd order, we show that the TAVEs can be reduced to an algebraic equation; when it is row diagonal and nonsingular with even order, we prove that the TAVEs is equivalent to a polynomial complementary problem. When no tensor is row diagonal, we formulate the TAVEs equivalently as polynomial optimization problems in two different ways. Each of them can be solved by Lasserre's hierarchy of semideflnite relaxations. The finite convergence properties are also discussed. Numerical experiments show the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the greatest common right divisor (GCRD) extraction from a set of polynomial matrices ... with coefficients in a generic field F and with common column dimension n. We give necessary and sufficient conditions for a matrix G(λ)∈F[λ]]lxn to be a GCRD using the Smith normal form of the m x n compound matrix P(λ) obtained by concatenating Pi(λ) vertically, where ... We also describe the complete set of degrees of freedom for the solution G(λ), and we link it to the Smith form and Hermite form of P(λ). We then give an algorithm for constructing a particular minimum size solution for this problem when F=C or R, using state-space techniques. This new method works directly on the coefficient matrices of P(λ)., using orthogonal transformations only. The method is based on the staircase algorithm, applied to a particular pencil derived from a generalized state-space model of P(λ). [ABSTRACT FROM AUTHOR]

The main result of this paper is the introduction of marked graphs and the marked graph polynomials (M-polynomial) associated with them. These polynomials can be defined via a deletion-contraction operation. These polynomials are a generalization of the W-polynomial, introduced by Noble and Welsh, and a specialization of the V-polynomial, introduced by Ellis-Monaghan and Moffatt. In addition, we describe an important specialization of the M-polynomial, which we call the D-polynomial. Furthermore, we present an efficient algorithm for computing the chromatic symmetric function of a graph in the star basis of symmetric functions. As an application of these tools, we prove that proper trees of diameter at most 5 are reconstructible from its chromatic symmetric function. [ABSTRACT FROM AUTHOR]

For many algorithmic problems on graphs of treewidth t, a standard dynamic programming approach gives algorithms with time and space complexity 2O(t)\cdot nO(1). It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form 2O(d)\cdot nO(1), where d is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity 2O(t)...nO(1) on graphs of treewidth t, but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. [ACM Trans. Algorithms, 18 (2022), 17] introduced the Cut\&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity 2O(t) · nO(1). Recently, Hegerfeld and Kratsch (STACS'20) showed that, for some of those problems, the Cut\&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time 2O(d) · nO(1) and polynomial space usage. However, several important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper, we clarify the situation by showing that Hamiltonian cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit 5d · nO(1)-time and polynomial space algorithms on graphs of treedepth d. The algorithms are randomized Monte Carlo with only false negatives. [ABSTRACT FROM AUTHOR]

In this paper, we consider the least element problem of a nonnegative solution set of a system of inequalities defined by a homogeneous polynomial mapping and a vector. In the set under consideration, the homogeneous polynomial mapping is defined by a tensor. When the tensor involved is square, the set under consideration is just the feasible region of the tensor complementarity problem (TCP). We first introduce the concept of the generalized Z-tensor, which is a natural generalization of the Z-tensor. Then, under the assumption that the considered set is nonempty and the tensor involved is a generalized Z-tensor, we propose an iterative method for finding the least element of the considered set. Specifically, by recognizing the position indices of positive components in the least element continuously, we solve a series of lower-dimensional system of tensor equations corresponding to these indices and prove that the least element of the set can be obtained within finite step iterations. When the tensor involved is square, the least element obtained is also a solution of the TCP. Compared with the existing methods for finding the least-element solution of the TCP with a Z-tensor, our method does not require any additional assumptions and has lower computational cost. Preliminary numerical experiments show that the proposed method is effective. [ABSTRACT FROM AUTHOR]

In this paper we propose a simple and unified framework to investigate the L2 -norm stability of the explicit Runge--Kutta discontinuous Galerkin (RKDG) methods when solving the linear constant-coefficient hyperbolic equations. Two key ingredients in the energy analysis are the temporal differences of numerical solutions in different Runge--Kutta stages and a matrix transferring process. Many popular schemes, including the fourth order RKDG schemes, are discussed in this paper to show that the presented technique is flexible and useful. Different performances in the L2 - norm stability of different RKDG schemes are carefully investigated. For some lower-degree piecewise polynomials, the monotonicity stability is proved if the stability mechanism can be provided by the upwind-biased numerical fluxes. Some numerical examples are also given. [ABSTRACT FROM AUTHOR]

In this paper we describe a generic spectral Petrov--Galerkin method that is sparse and strictly banded for any linear ordinary differential equation with polynomial coefficients. The method applies to all subdivisions of Jacobi polynomials (e.g., Chebyshev and Legendre), utilizes well-known recurrence relations of orthogonal polynomials, and leads to almost exactly the same discretized system of equations as the integration preconditioners [E. A. Coutsias, T. Hagstrom, and D. Torres, Math. Comp., 65 (1996), pp. 611--635] if this method was redesigned to make use of trial functions that satisfy a given problem's boundary conditions. A link between the new Petrov--Galerkin method and IP is revealed through a new recursion relation for Jacobi polynomials. Because of the strictly banded nature of all coefficient matrices, the new method extends easily and efficiently to multiple dimensions though the use of tensor product methods. [ABSTRACT FROM AUTHOR]

Assessing nonnegativity of multivariate polynomials over the reals, through the computation of certificates of nonnegativity, is a topical issue in polynomial optimization. This is usually tackled through the computation of sum of squares decompositions which rely on efficient numerical solvers for semidefinite programming. This method faces two difficulties. The first one is that the certificates obtained this way are approximate and then nonexact. The second one is due to the fact that not all nonnegative polynomials are sums of squares. In this paper, we build on previous works by Parrilo and Nie, Demmel, and Sturmfels who introduced certificates of nonnegativity modulo gradient ideals. We prove that, actually, such certificates can be obtained exactly over the rationals if the polynomial under consideration has rational coefficients, and we provide exact algorithms to compute them. We analyze the bit complexity of these algorithms and deduce bitsize bounds of such certificates. [ABSTRACT FROM AUTHOR]

Spectral methods, thanks to their high accuracy and the possibility of using fast algorithms, represent an effective way to approximate collisional kinetic equations in kinetic theory. On the other hand, the loss of some local invariants can lead to the wrong long time behavior of the numerical solution. We introduce in this paper a novel Fourier--Galerkin spectral method that improves the classical spectral method by making it conservative on the moments of the approximated distribution, without sacrificing its spectral accuracy or the possibility of using fast algorithms. The method is derived directly using a constrained best approximation in the space of trigonometric polynomials and can be applied to a wide class of problems where preservation of moments is essential. We then apply the new spectral method to the evaluation of the Boltzmann collision term and prove the spectral consistency and stability of the resulting Fourier--Galerkin approximation scheme. Various numerical experiments illustrate the theoretical findings. [ABSTRACT FROM AUTHOR]

n the article "A Rational QZ Method" by D. Camps, K. Meerbergen, and R. Vande-bril [SIAM J. Matrix Anal. Appl., 40 (2019), pp. 943--972], we introduced rational QZ (RQZ) methods. Our theoretical examinations revealed that the convergence of the RQZ method is governed by rational subspace iteration, thereby generalizing the classical QZ method, whose convergence relieson polynomial subspace iteration. Moreover the RQZ method operates on a pencil more general than Hessenberg---upper triangular, namely, a Hessenberg pencil, which is a pencil consisting of two Hessenberg matrices. However, the RQZ method can only be made competitive to advanced QZ implementations by using crucial add-ons such as small bulge multi shift sweeps, aggressive early deflation, and optimal packing. In this paper we develop these techniques for the RQZ method.In the numerical experiments we compare the results with state-of-the-art routines for the generalized eigenvalue problem and show that the presented method is competitive in terms of speed and accuracy. [ABSTRACT FROM AUTHOR]

Motivated by the concepts of the inverse Kazhdan--Lusztig polynomial and the equivariant Kazhdan--Lusztig polynomial, Proudfoot defined the equivariant inverse Kazhdan--Lusztig polynomial for a matroid. In this paper, we show that the equivariant inverse Kazhdan--Lusztig polynomial of a matroid is very useful for determining its equivariant Kazhdan--Lusztig polynomials, and we determine the equivariant inverse Kazhdan--Lusztig polynomials for Boolean matroids and uniform matroids. As an application, we give a new proof of Gedeon, Proudfoot, and Young's formula for the equivariant Kazhdan--Lusztig polynomials of uniform matroids. Inspired by Lee, Nasr, and Radcliffe's combinatorial interpretation for the ordinary Kazhdan--Lusztig polynomials of uniform matroids, we further present a new formula for the corresponding equivariant Kazhdan--Lusztig polynomials. [ABSTRACT FROM AUTHOR]

This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems that could not be solved by existing frameworks. To support this claim and illustrate the technique we include output-polynomial algorithms for several problems for which output-polynomial algorithms were not known, including the enumeration of maximal bipartite subgraphs, maximal k-degenerate subgraphs (for bounded k), maximal induced chordal subgraphs, and maximal induced trees. Using known techniques, such as reverse search, the space of all maximal solutions induces an implicit directed graph called "solution graph" or \supergraph," and solutions are enumerated by traversing it; however, nodes in this graph can have exponential out-degree, thus requiring exponential time to be spent on each solution. The novelty of proximity search is a formalization that allows us to define a better solution graph, and a technique, which we call canonical reconstruction, by which we can exploit the properties of given problems to build such graphs. This results in solution graphs whose nodes have significantly smaller (i.e., polynomial) out-degree with respect to existing approaches, but that remain strongly connected, so that all solutions can be enumerated in polynomial delay by a traversal. A drawback of this approach is the space required to keep track of visited solutions, which can be exponential; we further propose a technique to induce a parent-child relationship among solutions and achieve polynomial space when suitable conditions are met. [ABSTRACT FROM AUTHOR]

We determine the generic complete eigenstructures for n \times n complex symmetric matrix polynomials of odd grade d and rank at most r. More precisely, we show that the set of n Ã-- n complex symmetric matrix polynomials of odd grade d, i.e., of degree at most d, and rank at most r is the union of the closures of the [rd/2] + 1 sets of symmetric matrix polynomials having certain, explicitly described, complete eigenstructures. Then we prove that these sets are open in the set of nÃ--n complex symmetric matrix polynomials of odd grade d and rank at most r. In order to prove the previous results, we need to derive necessary and sufficient conditions for the existence of symmetric matrix polynomials with prescribed grade, rank, and complete eigenstructure in the case where all their elementary divisors are different from each other and of degree 1. An important remark on the results of this paper is that the generic eigenstructures identified in this work are completely different from the ones identified in previous works for unstructured and skew-symmetric matrix polynomials with bounded rank and fixed grade larger than 1, because the symmetric ones include eigenvalues while the others not. This difference requires using new techniques. [ABSTRACT FROM AUTHOR]

This paper investigates gradient recovery schemes for data defined on discretized manifolds. The proposed method, parametric polynomial preserving recovery (PPPR), does not require the tangent spaces of the exact manifolds which have been assumed for some significant gradient recovery methods in the literature. Another advantage of PPPR is that superconvergence is guaranteed without the symmetric condition which is required in the existing techniques. As an application, we show its capability of constructing an asymptotically exact a posteriori error estimator. Several numerical examples on two-dimensional surfaces are presented to support the theoretical results, and comparisons with existing methods are documented, showing that PPPR outperforms the other methods, in particular in the case of high curvature surfaces as well as mildly structured meshes. [ABSTRACT FROM AUTHOR]

In this paper, we study small-time local controllability of real analytic control-affine systems under small perturbations of their vector fields. Consider a real analytic control system Χ which is small-time locally controllable and whose reachable sets shrink with the polynomial rate of order N with respect to time. We will prove a general theorem which states that any real analytic control-affine system whose vector fields are perturbations of the vector fields of Χ with polynomials of order higher than N is again small-time locally controllable. In particular, we show that this result connects two long-standing open conjectures about small-time local controllability of systems. [ABSTRACT FROM AUTHOR]

This paper provides global exponential stabilization results by means of boundary feedback control for one dimensional nonlinear unstable reaction-diffusion partial differential equations (PDEs) with nonlinearities of superlinear growth. The class of systems studied are parabolic PDEs with nonlinear reaction terms that provide "damping" when the norm of the state is large (the class includes reaction-diffusion PDEs with polynomial nonlinearities). The case of Dirichlet actuation at one end of the domain is considered and a Control-Lypunov Functional construction is applied in conjunction with Stampacchia's truncation method. The paper also provides several important auxiliary results, among which is an extension of Wirtinger's inequality, used here for the construction of the Control-Lyapunov functional. [ABSTRACT FROM AUTHOR]

Factorization of regular Hermitian valued trigonometric polynomials (on the unit circle) and Hermitian valued polynomials (on the real line) have been studied well. In this paper we drop the condition of regularity and study factorization of singular Hermitian valued (trigonometric) polynomials. We subsequently apply the results to obtain a characterization of matrices with a circular higher rank numerical range and derive a new version of Anderson's theorem. As a special case, we obtain a new characterization of matrices with a circular numerical range. [ABSTRACT FROM AUTHOR]

We prove that we can always construct strongly minimal linearizations of an arbitrary rational matrix from its Laurent expansion around the point at infinity, which happens to be the case for polynomial matrices expressed in the monomial basis. If the rational matrix has a particular self-conjugate structure, we show how to construct strongly minimal linearizations that preserve it. The structures that are considered are the Hermitian and skew-Hermitian rational matrices with respect to the real line, and the para-Hermitian and para-skew-Hermitian matrices with respect to the imaginary axis. We pay special attention to the construction of strongly minimal linearizations for the particular case of structured polynomial matrices. The proposed constructions lead to efficient numerical algorithms for constructing strongly minimal linearizations. The fact that they are valid for any rational matrix is an improvement on any other previous approach for constructing other classes of structure preserving linearizations, which are not valid for any structured rational or polynomial matrix. The use of the recent concept of strongly minimal linearization is the key for getting such generality. Strongly minimal linearizations are Rosenbrock's polynomial system matrices of the given rational matrix, but with a quadruple of linear polynomial matrices (i.e., pencils): L(\lambda) := \Bigl[ A(\lambda) B(\lambda) C(\lambda) D(\lambda) \Bigr], where A(\lambda) is regular, and the pencils \bigl[ A(\lambda) B(\lambda) \bigr] and \Bigl[ A(\lambda) C(\lambda) \Bigr] have no finite or infinite eigenvalues. Strongly minimal linearizations contain the complete information about the zeros, poles, and minimal indices of the rational matrix and allow one to very easily recover its eigenvectors and minimal bases. Thus, they can be combined with algorithms for the generalized eigenvalue problem for computing the complete spectral information of the rational matrix. [ABSTRACT FROM AUTHOR]

The maximum clique problem is a classical optimization problem which finds many important applications. Some of the most theoretically interesting and computationally successful approaches to this problem are based on the Motzkin-Straus formulation, expressing the clique number in terms of the maximal value of a standard quadratic program. This intriguing relationship has also motivated significant developments in quadratic optimization, copositive programming, and complexity in nonlinear optimization. Inspired by such developments, this paper establishes a hierar-chy of polynomial programming formulations (Pk), k ∈ {2,..., ω} for the maximum clique problem, relating the clique number ω of a given graph to the global maximal value of a multilinear polynomial function fk(x) of degree k over the standard simplex in ℝ|V| . The case of k = 2 corresponds to the Motzkin-Straus formulation, and the hierarchical feature is in the fact that the set of local maxima of (Pk+1) is a subset of the set of local maxima of (Pk), k ∈ {2,..., ω - 1}. In particular, every local maximum of (Pω) is global. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a nonlocal nonlinear partial differential equation formally derived by Steinerberger [Proc. Amer. Math. Soc., 147 (2019), pp. 4733—4744] to model dynamics of roots of polynomials under differentiation. This partial differential equation is critical and bears striking resemblance to hydrodynamic models used to describe collective behavior of agents (such as birds, fish, or robots) in mathematical biology. We consider a periodic setting and show global regularity and exponential in time convergence to uniform density for solutions corresponding to strictly positive smooth initial data. [ABSTRACT FROM AUTHOR]

The problem of computing the distance of two real coprime polynomials to the set of polynomials with a nontrivial greatest common divisor (GCD) appears in computer algebra, signal processing, and control theory. It has been studied in the literature under the names approximate common divisor, ε-GCD, and distance to uncontrollability. Existing solution methods use di erent types of local optimization methods and require a user-defined initial approximation. In this paper, we propose a new method that allows us to include constraints on the coefficients of the polynomials. Moreover, the method proposed in the paper is more robust to the initial approximation than the Newton-type optimization methods available in the literature. Our approach consists of two steps: (1) reformulate the problem as a problem of determining the structured distance to singularity of an associated Sylvester matrix, and (2) integrate a system of ODEs, which describes the gradient associated to the functional to be minimized. [ABSTRACT FROM AUTHOR]

A successful computational approach for solving large-scale positive semidefinite (PSD) programs is to enforce PSD-ness on only a collection of submatrices. For our study, we let Sn,k be the convex cone of n x n symmetric matrices where all k x k principal submatrices are PSD. We call a matrix in this k-locally PSD. In order to compare Sn,k to the cone of PSD matrices, we study eigenvalues of k-locally PSD matrices. The key insight in this paper is that there is a convex cone H(ekn) so that if X ∈ Sn,k, then the vector of eigenvalues of X is contained in H(ekn). The cone H(ekn) is the hyperbolicity cone of the elementary symmetric polynomial ekn (where ekn(x) = Σs⊆[n]:|s|=k ∏i∈s xi) with respect to the all ones vector. Using this insight, we are able to improve previously known upper bounds on the Frobenius distance between matrices in Sn,k and PSD matrices. We also study the quality of the convex relaxation H(ekn). We first show that this relaxation is tight for the case of k = n -- 1, that is, for every vector in H(en-1n) there exists a matrix in Sn,n-1 whose eigenvalues are equal to the components of the vector. We then prove a structure theorem on nonsingular matrices in Sn,k all of whose k x k principal minors are zero, which we believe is of independent interest. This result shows shows that for 1 < k < n -- 1 "large parts" of the boundary of H(ekn) do not intersect with the eigenvalues of matrices in Sn,k. [ABSTRACT FROM AUTHOR]

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. In this paper, some monomials and trinomials over finite fields are employed to construct a number of families of cyclic codes. Lower bounds on the minimum weight of some families of the cyclic codes are developed. The minimum weights of other families of the codes constructed in this paper are determined. The dimensions of the codes are flexible. Many of the codes presented in this paper are optimal or almost optimal in the sense that they meet some bounds on linear codes. Open problems regarding cyclic codes from monomials and trinomials are also presented. [ABSTRACT FROM AUTHOR]

In this paper we propose an efficient method for solving the spherically constrained homogeneous polynomial optimization problem. The new approach has the following three main ingredients. First, we establish a block coordinate descent type search method for nonlinear optimization, with the novelty being that we accept only a block update that achieves the maximum improvement, hence the name of our new search method: maximum block improvement (MBI). Convergence of the sequence produced by the MBI method to a stationary point is proved. Second, we establish that maximizing a homogeneous polynomial over a sphere is equivalent to its tensor relaxation problem; thus we can maximize a homogeneous polynomial function over a sphere by its tensor relaxation via the MBI approach. Third, we propose a scheme to reach a KKT point of the polynomial optimization, provided that a stationary solution for the relaxed tensor problem is available. Numerical experiments have shown that our new method works very efficiently: for a majority of the test instances that we have experimented with, the method finds the global optimal solution at a low computational cost. [ABSTRACT FROM AUTHOR]

The structural data of any rational matrix R(λ), i.e., the structural indices of its poles and zeros together with the minimal indices of its left and right nullspaces, is known to satisfy a simple condition involving certain sums of these indices. This fundamental constraint was first proved by Van Dooren in 1978; here we refer to this result as the rational index sum theorem. An analogous result for polynomial matrices has been independently discovered (and rediscovered) several times in the past three decades. In this paper we clarify the connection between these two seemingly different index sum theorems, describe a little bit of the history of their development, and discuss their curious apparent unawareness of each other. Finally, we use the connection between these results to solve a fundamental inverse problem for rational matrices--for which lists L of prescribed structural data does there exist some rational matrix R(λ) that realizes exactly the list L? We show that Van Dooren's condition is the only constraint on rational realizability; that is, a list L is the structural data of some rational matrix R(λ) if and only if L satisfies the rational index sum condition. [ABSTRACT FROM AUTHOR]

This paper defines for the first time strong linearizations of arbitrary rational matrices, studies in depth properties and characterizations of such linear matrix pencils, and develops infinitely many examples of strong linearizations that can be explicitly and easily constructed from a minimal state-space realization of the strictly proper part of the considered rational matrix and the coefficients of the polynomial part. As a consequence, the results in this paper establish a rigorous foundation for the numerical computation of the complete structure of zeros and poles, both finite and at infinity, of any rational matrix by applying any well-known backward stable algorithm for generalized eigenvalue problems to any of the strong linearizations constructed in this work. [ABSTRACT FROM AUTHOR]

In this paper, a new C¹-conforming Petrov--Galerkin method for convection-diffusion equations is designed and analyzed. The trial space of our method is a C¹-conforming Qk (i.e., tensor product of polynomials of degree at most k) finite element space while the test space is taken as the L² (discontinuous) piecewise Qk-2 polynomial space. Existence and uniqueness of the numerical solution is proved and optimal error estimates in the L²-, H¹-, H²-norms are proved. In addition, a rigorous theoretical analysis establishes superconvergence properties of the new method and superconvergence points/lines are identified at mesh nodes (with order 2k-2 for both function value and derivatives), at roots of a special Jacobi polynomial, and at the Lobatto lines and Gauss lines. In order to reduce the global regularity requirement, interior a priori error estimates in the L²-, H¹-, H²-norms are derived. Numerical experiments are presented to confirm the theoretical findings. [ABSTRACT FROM AUTHOR]

This paper develops a fully discrete soft thresholding polynomial approximation over a general region, named Lasso hyperinterpolation. This approximation is an l1-regularized discrete least squares approximation under the same conditions of hyperinterpolation. Lasso hyperinterpolation also uses a high-order quadrature rule to approximate the Fourier coefficients of a given continuous function with respect to some orthonormal basis, and then it obtains its coefficients by acting a soft threshold operator on all approximated Fourier coefficients. Lasso hyperinterpolation is not a discrete orthogonal projection, but it is an efficient tool to deal with noisy data. We theoretically analyze Lasso hyperinterpolation for continuous and smooth functions. The principal results are twofold: The norm of the Lasso hyperinterpolation operator is bounded independently of the polynomial degree, which is inherited from hyperinterpolation, and the L2 error bound of Lasso hyperinterpolation is less than that of hyperinterpolation when the level of noise becomes large, which improves the robustness of hyperinterpolation. Explicit constructions and corresponding numerical examples of Lasso hyperinterpolation over intervals, discs, spheres, and cubes are given. [ABSTRACT FROM AUTHOR]

We consider a sequence of four variable polynomials by refining Stieltjes's continued fraction for Eulerian polynomials. Using combinatorial theory of Jacobi-type continued fractions and bijections, we derive various combinatorial interpretations in terms of permutation statistics for these polynomials, which include special kinds of descents and excedances in a recent paper of Baril and Kirgizov. As a byproduct, we derive several equidistribution results for permutation statistics, which enables us to confirm and strengthen a recent conjecture of Vajnovszki and also to obtain several companion permutation statistics for two bistatistics in a conjecture of Baril and Kirgizov. [ABSTRACT FROM AUTHOR]

We introduce a finite element method for numerical upscaling of second order elliptic equations with highly heterogeneous coefficients. The method is based on a mixed formulation of the problem and the concepts of the domain decomposition and the hybrid discontinuous Galerkin methods. The method utilizes three different scales: (1) the scale of the partition of the domain of the problem, (2) the scale of partition of the boundaries of the subdomains (related to the corresponding space of Lagrange multipliers), and (3) the fine-grid scale that is assumed to resolve the scale of the heterogeneous variation of the coefficients. Our proposed method gives a flexible framework that (1) couples independently generated multiscale basis functions in each coarse patch, (2) provides a stable global coupling independent of local discretization, physical scales, and contrast, and (3) allows avoiding any constraints [Arbogast et al., Multiscale Model. Simul., 6 (2007), pp. 319-346] on coarse spaces. In this paper, we develop and study a multiscale HDG method that uses polynomial and homogenization-based multiscale spaces. These coarse spaces are designed for problems with scale separation. In our subsequent paper, we plan to extend our flexible HDG framework to more challenging multiscale problems with nonseparable scales and high contrast and consider enriched coarse spaces that use appropriate local spectral problems. [ABSTRACT FROM AUTHOR]

In this paper we consider the issue of robust stability of a linear delayed feedback control (DFC) mechanism. In particular we consider a DFC for stabilizing fixed points of a smooth function f: Rm → Rm of the form x(k+1) = f(x(k))+u(k), where u(k) is given by the formula u(k) = -- ∑N-1j=1 ∊j(x(k--j)--x(k--j+1)). We associate with each fixed point of f an explicit polynomial whose Schur stability corresponds to the local asymptotic stability of the DFC at that fixed point. This polynomial is the characteristic polynomial of the Jacobian matrix of an auxiliary map from RmN to RmN and may be given in terms of the eigenvalues of the Jacobian of f at the fixed point. This enables us to evaluate the robustness of the control by considering over what possible sets of eigenvalues of the Jacobian of f the associated characteristic polynomials are Schur stable. We will show that, for a given control of the above form, stability is guaranteed only if the set of eigenvalues lies in a set in C of diameter less than or equal to 16 and whose connected components all have diameters less than or equal to 4. An explicit example indicating the sharpness of the diameter of connected components is provided. [ABSTRACT FROM AUTHOR]

This paper proposes a class of polynomial preconditioners for solving non-Hermitian linear systems of equations. The polynomial is obtained from a least-squares approximation in poly-nomial space instead of a standard Krylov subspace. The process for building the polynomial relies on an Arnoldi-like procedure in a small dimensional polynomial space and is equivalent to performing GMRES in polynomial space. It is inexpensive and produces the desired polynomial in a numerically stable way. A few improvements to the basic scheme are discussed including the development of a short-term recurrence and the use of compound preconditioners. Numerical experiments, including a test with challenging nonnormal three-dimensional Helmholtz equations and a few publicly available sparse matrices, are provided to illustrate the performance of the proposed preconditioners. [ABSTRACT FROM AUTHOR]

The probabilistic degree of a Boolean function f: { 0, 1}n - { 0, 1} is defined to be the smallest d such that there is a random polynomial P of degree at most d that agrees with f at each point with high probability. Introduced by Razborov [Mat. Zametki, 41 (1987), pp. 598--607], upper and lower bounds on probabilistic degrees of Boolean functions-specifically symmetric Boolean functions-have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems. In this paper, we characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero). [ABSTRACT FROM AUTHOR]

This paper studies bilevel polynomial optimization. We propose a method to solve it globally by using polynomial optimization relaxations. Each relaxation is obtained from the Karush-Kuhn-Tucker (KKT) conditions for the lower level optimization and the exchange technique for semi-infinite programming. For KKT conditions, Lagrange multipliers are represented as polynomial or rational functions. The Moment-sum-of-squares relaxations are used to solve the polynomial optimization relaxations. Under some general assumptions, we prove the convergence of the algorithm for solving bilevel polynomial optimization problems. Numerical experiments are presented to show the efficiency of the method. [ABSTRACT FROM AUTHOR]

A shear-locking free finite element discretization of the Reissner-Mindlin plate model is introduced. The rotation is discretized with piecewise polynomials of degree k + 2 while the degree k ≥ 0 is used for the displacement gradient. The method is closely related to the (generalized) Taylor-Hood pairing. In this case the general theory of saddle-point problems with penalty cannot exclude that the convergence speed for the rotation is limited by the lower rate expected for the displacement. However, in this paper, it is shown that the rotations are approximated at optimal order of accuracy. This superconvergence phenomenon is proved by means of the approximation properties of the Fortin operator for the Taylor-Hood element and the Galerkin projection. [ABSTRACT FROM AUTHOR]

In this paper we extend the polynomial time integration framework to include exponential integration for both partitioned and unpartitioned initial value problems. We then demonstrate the utility of the exponential polynomial framework by constructing a new class of parallel exponential polynomial block methods (EPBMs) based on the Legendre points. These new integrators can be constructed at arbitrary orders of accuracy and have improved stability compared to existing exponential linear multistep methods. Moreover, if the ODE right-hand-side evaluations can be parallelized efficiently, then high-order EPBMs are significantly more efficient at obtaining highly accurate solutions than exponential linear multistep methods and exponential spectral deferred correction methods of equivalent order. [ABSTRACT FROM AUTHOR]

Abstract. We consider the conductivity transmission problem in two dimensions with a simply connected inclusion of arbitrary shape. It is well known that the solvability of the transmission prob- lem can be established via the boundary integral formulation in which the Neumann-Poincar\e (NP) operator is involved. In this paper, we derive series expansions of the layer potential operators based on geometric function theory and exhibit a novel approach to the transmission problem. We frst construct a collection of harmonic basis functions by using the Faber polynomials associated with the simply connected inclusion. We then derive explicit series expansions of the layer potential operators with respect to the constructed basis functions. In particular, the NP operator becomes a doubly infnite, self-adjoint matrix operator, whose entry is explicitly given by the Grunsky coefcients cor- responding to the inclusion. By applying the fnite section method to this matrix formulation, we obtain an approximation scheme for the spectrum of the NP operator and the solution to the trans- mission problem. This scheme allows us to numerically compute, in a simple way, the spectrum of the NP operator for a smooth domain when the exterior conformal mapping is known. We additionally derive an explicit integral expression for the coefcients of the exterior conformal mapping so that for an inclusion of arbitrary shape, one can numerically compute the exterior conformal mapping by solving only one boundary integral equation and apply the proposed approach. We provide numerical examples to demonstrate the efectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper we propose a novel semidefinite programming based method to compute robust domains of attraction for state-constrained perturbed polynomial systems. A robust domain of attraction is a set of states such that every trajectory starting from it will approach an equilibrium while never violating a specified state constraint, regardless of the actual perturbation. The semidefinite program is constructed by relaxing a generalized Zubov's equation. The existence of solutions to the constructed semidefinite program is guaranteed, and there exists a sequence of solutions such that their strict one-sublevel sets inner-approximate the interior of the maximal robust domain of attraction in measure under appropriate assumptions. Some illustrative examples demonstrate the performance of our method. [ABSTRACT FROM AUTHOR]