Search

In this paper, we consider the problem of computing the entire sequence of the maximum degree of minors of a block-structured symbolic matrix (a generic partitioned polynomial matrix) A = (A α β x α β t d α β ) , where A α β is a 2 × 2 matrix over a field F , x α β is an indeterminate, and d α β is an integer for α = 1 , 2 , ⋯ , μ and β = 1 , 2 , ⋯ , ν , and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight bipartite matching problem. The main result of this paper is a combinatorial -time algorithm for computing the entire sequence of the maximum degree of minors of a (2 × 2) -type generic partitioned polynomial matrix of size 2 μ × 2 ν . We also present a minimax theorem, which can be used as a good characterization (NP ∩ co-NP characterization) for the computation of the maximum degree of minors of order k. Our results generalize the classical primal-dual algorithm (the Hungarian method) and minimax formula (Egerváry's theorem) for the maximum weight bipartite matching problem. [ABSTRACT FROM AUTHOR]

In this paper we provide a tetrahedra-free algorithm to compute low-cardinality quadrature rules with a given degree of polynomial exactness, positive weights and interior nodes on a polyhedral element with arbitrary shape. The key tools are the notion of Tchakaloff discretization set and the solution of moment-matching equations by Lawson-Hanson iterations for NonNegative Least-Squares. Several numerical tests are presented. The method is implemented in Matlab as open-source software. [ABSTRACT FROM AUTHOR]

In this paper, we develop the theoretical provisions of symmetric cryptographic algorithms based on the polynomial residue number system for the first time. The main feature of the proposed approach is that when reconstructing the polynomial based on the method of undetermined coefficients, multiplication is performed not on the found base numbers but on arbitrarily selected polynomials. The latter, together with pairwise coprime residues of the residue class system, serve as the keys of the cryptographic algorithm. Schemes and examples of the implementation of the developed polynomial symmetric encryption algorithm are presented. The analytical expressions of the cryptographic strength estimation are constructed, and their graphical dependence on the number of modules and polynomial powers is presented. Our studies show that the cryptanalysis of the proposed algorithm requires combinatorial complexity, which leads to an NP-complete problem. [ABSTRACT FROM AUTHOR]

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]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

We revisit the problem of finding a 1-restricted simple 2-matching of maximum cardinality. Recall that, given an undirected graph G = (V , E) , a simple 2-matching is a subset M ⊆ E of edges such that each node in V is incident to at most two edges in M . Clearly, each such M decomposes into a node-disjoint collection of paths and circuits. M is called 1-restricted if it contains no isolated edges (i.e. paths of length one). A combinatorial polynomial algorithm for finding such M of maximum cardinality and also a min-max relation were devised by Hartvigsen. It was shown that finding such M amounts to computing a (not necessarily 1-restricted) simple 2-matching M 0 of maximum cardinality and subsequently altering it into M of the same cardinality so as to minimize the number of isolated edges. While the first phase (which computes M 0 ) runs in O E V time, the second one (which turns M 0 into M ) requires O (V E) time. In this paper we apply the general blocking augmentation approach (initially introduced, e.g., for bipartite matchings by Hopcroft and Karp, and also by Dinic) and present a novel algorithm that reduces the time needed for the second phase to O E V thus completely closing the gap between 1-restricted and unrestricted cases. [ABSTRACT FROM AUTHOR]

Detecting the cosmic 21 cm signal from epoch of reionization has always been a difficult task. Although the Galactic foreground can be regarded as a smooth power-law spectrum, due to the chromaticity of the antenna, additional structure will be introduced into the global spectrum, making the polynomial fitting algorithm perform poorly. In this paper, we introduce an improved polynomial fitting algorithm – the Vari-Zeroth-Order Polynomial (VZOP) fitting and use it to fit the simulation data. This algorithm is developed for the upcoming low-frequency anechoic chamber experiment, yet it is a general method suitable for application in any single antenna-based global 21 cm signal experiment. VZOP defines a 24-h averaged beam model that brings information about the antenna beam into the polynomial model. Assuming that the beam can be measured, VZOP can successfully recover the 21 cm absorption feature, even if the beam is extremely frequency-dependent. In real observations, due to various systematics, the corrected measured beam contains residual errors that are not completely random. Assuming the errors are frequency-dependent, VZOP is capable of recovering the 21 cm absorption feature even when the error reaches 10 per cent. Even in the most extreme scenario where the errors are completely random, VZOP can at least give a fitting result that is not worse than the common polynomial fitting. In conclusion, the fitting effect of VZOP depends on the structure of the error and the accuracy of the beam measurement. [ABSTRACT FROM AUTHOR]

A new algorithm is proposed in this paper for computing the nearest polynomial to multiple given polynomials with a given zero in the real case, where the distance between polynomials is defined by the weighted ℓ 2 , q norm (0 < q ≤ 2). First, the problem is formulated as a univariate constrained non-convex minimization problem, where prior information of the coefficients of the polynomial can be embedded by selecting proper weights. Then, an iteratively reweighted algorithm is designed to solve the obtained problem, and also the convergence and rate of convergence are uniformly demonstrated for all q in (0 , 2 ]. Since all the existing methods for computing the nearest polynomial to multiple given polynomials with a given zero are limited to the real case, we ingeniously extend the results to the complex case. Finally, two representative examples that separately compute the nearest real and complex polynomials are presented to show the effectiveness of the proposed algorithm. • A weighted ℓ 2 , q -norm based minimization problem is constructed with prior information of polynomial embedded. • After converting the problem into a univariate problem, an iteratively reweighted algorithm is proposed to solve it. • Using properties of a concave function, convergence and rate of convergence of the proposed algorithm are provided. • It is the first time to study computation of the nearest polynomial to multiple given polynomials with a given zero in the complex case. [ABSTRACT FROM AUTHOR]

Steepest descent methods combining complex contour deformation with numerical quadrature provide an efficient and accurate approach for the evaluation of highly oscillatory integrals. However, unless the phase function governing the oscillation is particularly simple, their application requires a significant amount of a priori analysis and expert user input, to determine the appropriate contour deformation, and to deal with the non-uniformity in the accuracy of standard quadrature techniques associated with the coalescence of stationary points (saddle points) with each other, or with the endpoints of the original integration contour. In this paper we present a novel algorithm for the numerical evaluation of oscillatory integrals with general polynomial phase functions, which automates the contour deformation process and avoids the difficulties typically encountered with coalescing stationary points and endpoints. The inputs to the algorithm are simply the phase and amplitude functions, the endpoints and orientation of the original integration contour, and a small number of numerical parameters. By a series of numerical experiments we demonstrate that the algorithm is accurate and efficient over a large range of frequencies, even for examples with a large number of coalescing stationary points and with endpoints at infinity. As a particular application, we use our algorithm to evaluate cuspoid canonical integrals from scattering theory. A Matlab implementation of the algorithm is made available and is called PathFinder. • An algorithm for the evaluation of oscillatory integrals with polynomial phase. • The algorithm automates the numerical steepest descent method. • Our implementation is robust and efficient across all frequencies. [ABSTRACT FROM AUTHOR]

We develop the first algorithm for computing rational solutions of scalar integro-differential equations with polynomial coefficients. It starts by finding the possible poles of a rational solution. Then, bounding the order of each pole and solving an algebraic linear system, we compute the singular part of rational solutions at each possible pole. Finally, using partial fraction decomposition, the polynomial part of rational solutions is obtained by computing polynomial solutions of a non-homogeneous scalar integro-differential equation with a polynomial right-hand side. The paper is illustrated by examples where the computations are done with our Maple implementation. [ABSTRACT FROM AUTHOR]

Mixed trigonometric-polynomials (MTPs) are functions of the form f (x , sin ⁡ x , cos ⁡ x) where f is a trivariate polynomial with rational coefficients, and the argument x ranges over the reals. In this paper, an algorithm "isolating" all the real roots of an MTP is provided and implemented. It automatically divides the real roots into two parts: one consists of finitely many roots in an interval [ μ − , μ + ] while the other consists of countably many roots in R ﹨ [ μ − , μ + ]. For the roots in [ μ − , μ + ] , the algorithm returns isolating intervals and corresponding multiplicities while for those greater than μ + , it returns finitely many mutually disjoint small intervals I i ⊂ [ − π , π ] , integers c i > 0 and multisets of root multiplicity { m j , i } j = 1 c i such that any root > μ + is in the set (∪ i ∪ k ∈ N (I i + 2 k π)) and any interval I i + 2 k π ⊂ (μ + , ∞) contains exactly c i distinct roots with multiplicities m 1 , i ,... , m c i , i , respectively. The efficiency of the algorithm is shown by experiments. The method used to isolate the roots in [ μ − , μ + ] is applicable to any other bounded interval as well. The algorithm takes advantages of the weak Fourier sequence technique and deals with the intervals period-by-period without scaling the coordinate so to keep the length of the sequence short. The new approaches can easily be modified to decide whether there is any root, or whether there are infinitely many roots in unbounded intervals of the form (− ∞ , a) or (a , ∞) with a ∈ Q. [ABSTRACT FROM AUTHOR]

A 2D rigidity circuit is a minimal graph G = (V , E) supporting a non-trivial stress in any generic placement of its vertices in the Euclidean plane. All 2D rigidity circuits can be constructed from K 4 graphs using combinatorial resultant (CR) operations. A combinatorial resultant tree (CR-tree) is a rooted binary tree capturing the structure of such a construction. The CR operation has a specific algebraic interpretation, where an essentially unique circuit polynomial is associated to each circuit graph. Performing Sylvester resultant operations on these polynomials is in one-to-one correspondence with CR operations on circuit graphs. This mixed combinatorial/algebraic approach led recently to an effective algorithm for computing circuit polynomials. Its complexity analysis remains an open problem, but it is known to be influenced by the depth and shape of CR-trees in ways that have only partially been investigated. In this paper, we present an effective algorithm for enumerating all the CR-trees of a given circuit with n vertices. Our algorithm has been fully implemented in Mathematica and allows for computational experimentation with various optimality criteria in the resulting, potentially exponentially large collections of CR-trees. [ABSTRACT FROM AUTHOR]

The fast and efficient operation of post-quantum cryptographic algorithms has become an important research topic, especially with the recent developments and the process of the PQC Standardization Project by NIST. Various algorithms based on lattices are chosen to be finalists in this project. Number Theoretic Transform (NTT), Toom–Cook, Karatsuba, and Toeplitz matrix–vector product (TMVP) are considered in order to efficiently perform multiplications in quotient polynomial rings required by the cryptographic schemes based on lattices. In this paper, we propose a 5-way split TMVP-based algorithm for multiplication in polynomial quotient rings and determine its computational complexity. The new algorithm is derived from a 5-term polynomial multiplication algorithm using 13 multiplications with coefficients of only 1 or -1 that provide efficiency. We also implement it for all parameter sets of NTRU. The results show that we have up to 34%, 35%, and 157% speed-up against Toom4-Karatsuba implementation in key generation, encapsulation, and decapsulation, respectively. [ABSTRACT FROM AUTHOR]

By a result of Latimer and MacDuffee, there are a finite number of equivalence classes of n × n matrices over F q [ T ] with minimum polynomial p (X) , where p is an n th degree polynomial, irreducible over F q [ T ]. In this paper, we develop an algorithm for finding a canonical representative of each matrix class, for p (X) = X 2 − Γ X − Δ ∈ F q [ T ] [ X ]. [ABSTRACT FROM AUTHOR]