Search

The paper presents a technique for determining the time index of growth of the slope of reverse voltage for double insulated cables, based on the body of the theory of series. It is proved that in the vicinity of the extremum point (maximum) the function of the reverse voltage is approximated by polynomials of the nth power. It is proposed to use second-degree polynomials for practical calculations. The method for calculating relevant indicators is illustrated using real data. Analysis of deviations made it possible to conclude that the calculation method proposed in the paper is far more accurate. In the final part of the study, it was concluded that there is a promising outlook for further development of methodological guidelines for determining complex indices of the remaining life of the cable, including but not limited to the use of various mathematical methods. [ABSTRACT FROM AUTHOR]

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]

In this paper, we take an algebraic approach to the generalized DGHV scheme without using bootstrapping technique. We investigate the homomorphic evaluation algorithm in detail and provide several sufficient conditions for correct homomorphic evaluation of arbitrary polynomial circuits. Compared with the bootstrapping procedure, we show that our approach is much simpler and more efficient. Moreover, we prove that both of the key sizes are actually bounded above and that these upper-bounds depend only on the plaintext space and the security parameter. Hence we need only one pair of secret key and public key for correct homomorphic evaluation of all polynomial circuits, which implies the generalized DGHV scheme is a fully homomorphic encryption in itself. Thus our approach shows that the generalized DGHV scheme provides extremely simple and efficient algorithms. [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]

The aim of this paper is to give many new and elegant formulas for a new class of generalized Fubini polynomials with the aid of generating functions and their functional equations. By using these formulas, some computational algorithms involving a new class of generalized Fubini polynomials and special polynomials and numbers are constructed. Using these algorithms, some values of these numbers and polynomials are computed. Finally, some remarks and observations on the results of this paper are presented. [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]

Even-cycle matroids are elementary lifts of graphic matroids and even-cut matroids are elementary lifts of cographic matroids. We present a polynomial algorithm to check if a binary matroid is an even-cycle matroid and we present a polynomial algorithm to check if a binary matroid is an even-cut matroid. These two algorithms rely on a polynomial algorithm (to be described in a pair of follow-up papers) to check if a binary matroid is pinch-graphic. [ABSTRACT FROM AUTHOR]

When exploring the literature, it can be observed that the operator obtained when applying Newton-like root finding algorithms to the quadratic polynomials z2 − c has the same form regardless of which algorithm has been used. In this paper, we justify why this expression is obtained. This is done by studying the symmetries of the operators obtained after applying Newton-like algorithms to a family of degree d polynomials p(z) = zd − c. Moreover, we provide an iterative procedure to obtain the expression of new Newton-like algorithms. We also carry out a dynamical study of the given generic operator and provide general conclusions of this type of methods. [ABSTRACT FROM AUTHOR]

Considering a multivariate polynomial ideal over a given field as a vector space, we investigate for such an ideal a particular linear basis, a so-called staggered linear basis, which contains a Gröbner basis as well. In this paper, we present a simple and efficient algorithm to compute a staggered linear basis. The new framework is equipped with some novel criteria (including both Buchberger's criteria) to detect superfluous reductions. The proposed algorithm has been implemented in Maple, and we provide an illustrative example to show how it works. Finally, the efficiency of this algorithm compared to the existing methods is discussed via a set of benchmark polynomials. [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]

Holonomic sequences are widely studied as many objects interesting to mathematicians and computer scientists are in this class. In the univariate case, these are the sequences satisfying linear recurrences with polynomial coefficients and also referred to as D -finite sequences. A subclass are C -finite sequences satisfying a linear recurrence with constant coefficients. We investigate the set of sequences which satisfy linear recurrence equations with coefficients that are C -finite sequences and call them C 2 -finite sequences. These sequences are a natural generalization of holonomic sequences. In this paper, we show that C 2 -finite sequences form a difference ring and provide methods to compute in this ring. Furthermore, we provide an analogous construction for D 2 -finite sequences, i.e., sequences satisfying a linear recurrence with holonomic coefficients. We show that these constructions can be iterated and obtain an increasing chain of difference rings. [ABSTRACT FROM AUTHOR]

Aiming at the precision loss problem of most low-complexity Root-MUSIC algorithms at present, a low-complexity Root-MUSIC algorithm with precision compensation ability is studied and proposed. The algorithm reconstructs the autocorrelation matrix with Toeplitz shape according to the first row of the approximate data observation matrix obtained by finite snapshots, so that the reconstructed autocorrelation matrix has Hermitian property. After decomposing the reconstructed autocorrelation matrix, the noise subspace is obtained, the noise subspace is flipped and split, a new root-finding polynomial is reconstructed, and then the DOA estimated value is obtained by the root-finding method. The algorithm proposed in this paper using Toeplitz matrix reconstruction and root polynomial reduction effectively improves the DOA estimation accuracy of the improved Root-MUSIC algorithm. And the time complexity of the improved algorithm is no higher than that of previous algorithms. Under different incident sources and sampling snapshots, the algorithm proposed in this paper also shows stronger robustness and stability. [ABSTRACT FROM AUTHOR]

In the Quantum Key Distribution (QKD) network, authentication protocols play a critical role in safeguarding data interactions among users. To keep pace with the rapid advancement of QKD technology, authentication protocols must be capable of processing data at faster speeds. The Secure Hash Algorithm (SHA), which functions as a cryptographic hash function, is a key technology in digital authentication. Irreducible polynomials can serve as characteristic functions of the Linear Feedback Shift Register (LFSR) to rapidly generate pseudo-random sequences, which in turn form the foundation of the hash algorithm. Currently, the most prevalent approach to hardware implementation involves performing block computations and pipeline data processing of the Toeplitz matrix in the Field-Programmable Gate Array (FPGA) to reach a maximum computing rate of 1 Gbps. However, this approach employs a fixed irreducible polynomial as the characteristic polynomial of the LFSR, which results in computational inefficiency as the highest bit of the polynomial restricts the width of parallel processing. Moreover, an attacker could deduce the irreducible polynomials utilized by an algorithm based on the output results, creating a serious concealed security risk. This paper proposes a method to use FPGA to implement variational irreducible polynomials based on a hashing algorithm. Our method achieves an operational rate of 6.8 Gbps by computing equivalent polynomials and updating the Toeplitz matrix with pipeline operations in real-time, which accelerates the authentication protocol while also significantly enhancing its security. Moreover, the optimization of this algorithm can be extended to quantum randomness extraction, leading to a considerable increase in the generation rate of random numbers. [ABSTRACT FROM AUTHOR]

This paper considers linear and nonlinear fractional delay Volterra integrodifferential equation of order ρ in the Atangana–Beleanu–Caputo (ABC) sense. We used continuous Laplace transform (CLT) to find equivalent Volterra integral equations that have been used together with the Arzela–Ascoli theorem and Schauder's fixed point theorem to prove the local existence solution. Moreover, the obtained Volterra integral equations and the contraction mapping theorem have been successfully applied to construct and prove the global existence and uniqueness of the solution for the considered fractional delay integrodifferential equation (FDIDE). The Galerkin algorithm instituted within shifted Legendre polynomials (SLPs) is applied in the approximation procedure for the corresponding delay equation. Indeed, by this algorithm, we get algebraic system models and by solving this system we gained the approximated nodal solution. The reliability of the method and reduction in the size of the computational work give the algorithm wider applicability. Linear and nonlinear examples are included with some tables and figures to show the effectiveness of the method in comparison with the exact solutions. Finally, some valuable notes and details extracted from the presented results were presented in the last part, with the sign to some of our future works. [ABSTRACT FROM AUTHOR]

Flagged Schur modules generalize the irreducible representations of the general linear group under the action of the Borel subalgebra. Their characters include many important generalizations of Schur polynomials, such as Demazure characters, flagged skew Schur polynomials, and Schubert polynomials. In this paper, we prove the characters of flagged Schur modules can be computed using a simple combinatorial algorithm due to Kohnert if and only if the indexing diagram is northwest. This gives a new proof that characters of flagged Schur modules are nonnegative sums of Demazure characters and gives a representation theoretic interpretation for Kohnert polynomials. [ABSTRACT FROM AUTHOR]

An added edge to a graph is called an inset edge. Predicting k inset edges, which minimize the average distance of a graph, is known to be NP-Hard. However, when k = 1 , the complexity of the problem is polynomial. In this paper, some tools for a precise analysis of the effect of inset edges on the tree's average distance are established. Using the tools, one can avoid using the distance matrix for better performance of algorithms. Here, some applications of the tools and a tight bound for the change of average distance when an inset edge is added to a tree are presented. [ABSTRACT FROM AUTHOR]

For each n, let RD(n) denote the minimum d for which there exists a formula for the general polynomial of degree n in algebraic functions of at most d variables. In this paper, we recover an algorithm of Sylvester for determining non-zero solutions of systems of homogeneous polynomials, which we present from a modern algebro-geometric perspective. We then use this geometric algorithm to determine improved thresholds for upper bounds on RD(n). [ABSTRACT FROM AUTHOR]

Theory of quasi-orthogonal polynomials is significantly related to constructing vector Padé approximations. The present paper introduces an efficient procedure to compute adjacent families of quasi-orthogonal polynomials as defined in Sadaka (Appl. Numer. Math. 21:57–70, 1996) and Sadaka (Appl. Numer. Math. 24:483–499, 1997). The derived algorithm uses short recursive relations whose coefficients are written in terms of lower triangular block determinants. The strategy of computing such determinants is given and analyzed. [ABSTRACT FROM AUTHOR]

For a large class of closed orientable 3-manifolds, we present a polynomial algorithm to go from a triangulation to a framed link presenting the same manifold. The algorithm applies whenever we can get a resoluble gem from the triangulation. Most minimal gems have this property (about 95% of gems in our complete catalogue up to 28 vertices). From the gems which fail, nothing prevents another gem from inducing the same 3-manifold to be resoluble. We leave as an open problem presenting a 3-manifold which is not induced by a resoluble gem. This paper is an application of the theory of gems to 3-manifold topology. [ABSTRACT FROM AUTHOR]

This paper studies the problem of deterministic rank-one matrix completion. It is known that the simplest semidefinite programming relaxation, involving minimization of the nuclear norm, does not in general return the solution for this problem. In this paper, we show that in every instance where the problem has a unique solution, one can provably recover the original matrix through the level 2 Lasserre relaxation with minimization of the trace norm. We further show that the solution of the proposed semidefinite program is Lipschitz stable with respect to perturbations of the observed entries, unlike more basic algorithms such as nonlinear propagation or ridge regression. Our proof is based on recursively building a certificate of optimality corresponding to a dual sum-of-squares (SoS) polynomial. This SoS polynomial is built from the polynomial ideal generated by the completion constraints and the monomials provided by the minimization of the trace. The proposed relaxation fits in the framework of the Lasserre hierarchy, albeit with the key addition of the trace objective function. Finally, we show how to represent and manipulate the moment tensor in favorable complexity by means of a hierarchical low-rank factorization. [ABSTRACT FROM AUTHOR]

Approximate polynomial GCD (greatest common divisor) of polynomials with a priori errors on their coefficients, is one of interesting problems in Symbolic-Numeric Computations. In fact, there are many known algorithms: QRGCD, UVGCD, STLN based methods, Fastgcd and so on. The fundamental question of this paper is "which is the best?" from the practical point of view, and subsequently "is there any better way?" by any small extension, any effect by pivoting, and any combination of sub-routines along the algorithms. In this paper, we consider a framework that covers those algorithms and their sub-routines, and makes their sub-routines being interchangeable between the algorithms (i.e. disassembling the algorithms and reassembling their parts). By this framework along with/without small new extensions and a newly adapted refinement sub-routine, we have done many performance tests and found the current answer. In summary, 1) UVGCD is the best way to get smaller tolerance, 2) modified Fastgcd is better for GCD that has one or more clusters of zeros with large multiplicity, and 3) modified ExQRGCD is better for GCD that has no cluster of zeros. [ABSTRACT FROM AUTHOR]

This paper introduces a novel population-based vortex search algorithm (PVS) to improve the weakness of the global search capability of the original Vortex Search (VS) algorithm which is a simple and efficient physics-based metaheuristic and originally has a single-solution-based structure. Single-solution-based metaheuristics perform a local search in the neighborhood of a single solution, whereas population-based metaheuristics conduct the search process by creating several candidate solutions at different points in the search space. The fast-running structures of single-solution-based algorithms may cause the search process to get stuck in the local optimum in some cases. The proposed algorithm transforms VS into a population-based structure with a location update operator and the polynomial mutation operator. Also, the strategy of generating solutions based on the radius reduction mechanism around a center is maintained. Furthermore, two variants of PVS, called PVS_a and PVS_b, are presented in this study. The performance of the proposed approach is investigated by applying a set of experimental series. Three different benchmark sets involving (i) 20 classical benchmark functions, (ii) 29 CEC2017 test functions, and (iii) 10 CEC2019 test functions are employed in experiments. In addition, four real-world-constrained optimization problems are used to evaluate the effectiveness of PVS. Considering the experimental results obtained from the comparison of the proposed algorithm with both state-of-the-art and recent metaheuristics, the developed PVS_a algorithm provides highly quite promising and superior outcomes in solution quality and robustness. [ABSTRACT FROM AUTHOR]

Conflict-free q -colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the Minimum Conflict-free q-Colouring problem. Given a graph G and a fixed constant q , Minimum Conflict-free q-Colouring is to find a conflict-free q -colouring of G that minimizes the number of coloured vertices. We study the parameterized complexity of the Minimum Conflict-free q-Colouring problem when parameterized by structural parameters like treewidth and vertex cover of G. We give an FPT algorithm for Minimum Conflict-free q-Colouring parameterized by treewidth and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH). Using standard kernelization lower bound techniques, it is easy to see that Minimum Conflict-free q-Colouring parameterized by treewidth does not admit polynomial kernels. We extend this result for a larger parameter namely the vertex cover of G , when q > 1. [ABSTRACT FROM AUTHOR]

This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points. It is based on solving Lasserre's hierarchy of semidefinite relaxations. Under some genericity assumptions on defining polynomials, we show that: (i) if there exists a saddle point, our algorithm can get one by solving a finite hierarchy of Lasserre-type semidefinite relaxations; (ii) if there is no saddle point, our algorithm can detect its nonexistence. [ABSTRACT FROM AUTHOR]

In this paper, we propose an algorithm for solving the Cauchy problem for a two-dimensional difference equation with constant coefficients at a point, based on its coefficients and the initial data for the Cauchy problem, which are defined in a "strip." For this purpose, computer algebra methods are employed. To automate the process of computing the solution, the algorithm is implemented in MATLAB, with the input data being the matrix of coefficients of the two-dimensional polynomial difference equation, the coordinates of the initial data matrix (which defines the structure of the difference equation), and the coordinates of the point that determines the dimension of the initial data matrix. The output of the algorithm is a solution of the Cauchy problem (with the initial data defined in a "strip") for the two-dimensional difference equation, which is a function value at the desired point. [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]

We study the following problem. Given a multiset M of non-negative integers, decide whether there exist and, in the positive case, compute two non-trivial multisets whose Minkowski sum is equal to M. The Minkowski sum of two multisets A and B is a multiset containing all possible sums of any element of A and any element of B. This problem was proved to be NP-complete when multisets are replaced by sets. This version of the problem is strictly related to the factorization of boolean polynomials that turns out to be NP-complete as well. When multisets are considered, the problem is equivalent to the factorization of polynomials with non-negative integer coefficients. The computational complexity of both these problems is still unknown. The main contribution of this paper is a heuristic technique for decomposing multisets of non-negative integers. Experimental results show that our heuristic decomposes multisets of hundreds of elements within seconds, independently of the magnitude of numbers belonging to the multisets. Our heuristic can also be used for factoring polynomials in N[x]. We show that, when the degree of the polynomials gets larger, our technique is much faster than the state-of-the-art algorithms implemented in commercial software like Mathematica and MatLab. [ABSTRACT FROM AUTHOR]

The Horner and Goertzel algorithms are frequently used in polynomial evaluation. Each of them can be less expensive than the other in special cases. In this paper, we present a new compensated algorithm to improve the accuracy of the Goertzel algorithm by using error-free transformations. We derive the forward round-off error bound for our algorithm, which implies that our algorithm yields a full precision accuracy for polynomials that are not too ill-conditioned. A dynamic error estimate in our algorithm is also presented by running round-off error analysis. Moreover, we show the cases in which our algorithms are less expensive than the compensated Horner algorithm for evaluating polynomials. Numerical experiments indicate that our algorithms run faster than the compensated Horner algorithm in those cases while producing the same accurate results, and our algorithm is absolutely stable when the condition number is smaller than 10 16 . An application is given to illustrate that our algorithm is more accurate than MATLAB's fft function. The results show that the relative error of our algorithm is from 10 15 to 10 17 , and that of the fft was from 10 12 to 10 15 . [ABSTRACT FROM AUTHOR]

Whereas set-valued tableaux are the combinatorial objects associated to stable Grothendieck polynomials, hook-valued tableaux are associated with stable canonical Grothendieck polynomials. In this paper, we define a novel uncrowding algorithm for hook-valued tableaux. The algorithm "uncrowds" the entries in the arm of the hooks, and yields a set-valued tableau and a column-flagged increasing tableau. We prove that our uncrowding algorithm intertwines with crystal operators. An alternative uncrowding algorithm that "uncrowds" the entries in the leg instead of the arm of the hooks is also given. As an application of uncrowding, we obtain various expansions of the canonical Grothendieck polynomials. [ABSTRACT FROM AUTHOR]

Restoring the controllability of networked control systems is a fundamental issue that needs to be settled, especially when malicious attacks or malfunctions occur. Previous studies tried to address such an issue by adding extra driver nodes or rewiring edges, which will inevitably change the original network structure. In this paper, an algorithm to restore the controllability of networked systems while preserving the integrity of the original network structure is proposed. Specifically, a static uncontrollable network will be transformed into a controllable temporal network by means of the cactus‐based segmentation method. The original problem will be equivalent to the classical set cover problem, which is known to be NP‐Hard, if the least number of segmentations is considered. An approximation algorithm with polynomial time complexity is proposed and it is proved that the solution to the problem is two‐optimal. Finally, simulations are carried out to verify the effectiveness and feasibility of the proposed algorithm. [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]

In this paper, we present a method of programmatic identification of complex roots of polynomials with complex coefficients without specifying the domain of localization of their roots. The method is based on the algorithm of stable address sorting with minimal amount of calculations. Numerical ranges of the real and imaginary parts of the roots are programmatically determined, the roots are identified without loss of significant figures of the mantissa in the format of presentation of numerical data. [ABSTRACT FROM AUTHOR]

This paper contains the computational approach based on Mott polynomials together with the two‐dimensional Legendre–Gauss (LG) quadrature rule for fractal‐fractional two‐dimensional Fredholm–Volterra (FF‐2D‐FV) integro‐differential equations. Furthermore, we applied the modified operational matrices of integration and fractional derivative in the process of the numerical algorithm to get the approximate solution with high accuracy. The fractal‐fractional derivative is defined in the Atangana–Riemann–Liouville sense. Besides, we estimate the error of the method in Sobolev space. Ultimately, to prove the theoretical claim, we represent the numerical results in the form of tables and diagrams. [ABSTRACT FROM AUTHOR]

Many classes of engineering problems focus on the process of calibrating mathematical models using observed data. The enormous progress of scientific computation and data-mining techniques has allowed the search for accurate mathematical models from experimental data using algorithms. Among them, the evolutionary polynomial regression (EPR) is an artificial intelligence (AI) technique that merges genetic algorithms (GAs) and regression techniques such as ordinary least square (OLS). This paper presents a robust and well-conditioned EPR technique to remove potential outliers and leverage points included in any biased data set. This hybrid approach combines bisquare, Huber, and Cauchy robust multivariate techniques with GAs and the Akaike weight-based method to assess the optimal polynomial model while limiting the impact of the data bias. The robust techniques will define the parameters, the GAs will determine the exponents, and the Akaike weight-based method will evaluate the relative importance of each observed variable of the proposed model. As a case study, a shear strength data set of RC beams without stirrups is used to compare the standard EPR algorithm with the new proposed hybrid methodology. Furthermore, the optimal robust model is compared with different benchmark formulations to highlight its accuracy and consistency. The proposed hybrid technique can be adopted as a mathematical tool for many engineering problems, providing an unbiased prediction of the observed variable. Furthermore, the shear strength equation that provides the best compromise between accuracy and complexity allows its potential use in many engineering practices and building codes. [ABSTRACT FROM AUTHOR]

Metamodels are an important tool in simulation analysis as they can provide insight about the behavior of the simulation response. Modeling the response with low-degree polynomial segments allows the identification of different behavior zones and the parameters still have relation with the physical world. The purpose of this paper is to extend the use of segmented polynomial functions for simulation metamodeling, where the segments have at most identical value and slope at the breaks. Our approach is to build segmented polynomials metamodels where the hypothesis of degree and continuity of splines are less exigent, allowing more flexibility of the approximation. When breaks are known, constrained least squares are used for metamodel estimation, taking into account the linear formulation of the problem. If breaks have to be estimated, the unconstrained nonlinear regression theory is used, when it can be applied. Otherwise, the estimation is performed using an iterative algorithm which is applied repeatedly in a cyclic manner for estimating the breaks, and jackknifing yields the confidence intervals. [ABSTRACT FROM AUTHOR]

The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned 1, while the rest are all assigned 0. We can generalise this problem further by defining that a C j clause is solved iff exactly j of the literals in the clause are 1 and all others are 0. We now introduce the family of Generalised Exact Satisfiability problems called G i XSAT as the problem to check whether a given instance consisting of C j clauses with j ∈ { 0 , 1 , ... , i } for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve G i XSAT, for i ∈ { 2 , 3 , 4 } , in O (1.3674 n) time, O (1.5687 n) time and O (1.6545 n) time, respectively, using polynomial space, where n is the number of variables. This improves the current state of the art for polynomial space algorithms from O (1.4203 n) time for G2XSAT by Zhou, Jiang and Yin and from O (1.6202 n) time for G3XSAT by Dahllöf and from O (1.6844 n) time for G4XSAT which was by Dahllöf as well. In addition, we present faster exact algorithms solving G2XSAT, G3XSAT and G4XSAT in O (1.3188 n) time, O (1.3407 n) time and O (1.3536 n) time respectively at the expense of using exponential space. [ABSTRACT FROM AUTHOR]