Approximate factorization of multivariate polynomials using singular value decomposition

We describe the design, implementation and experimental evaluation of new algorithms for computing the approximate factorization of multivariate polynomials with complex coefficients that contain numerical noise. Our algorithms are based on a generalization of the differential forms introduced by W. Ruppert and S. Gao to many variables, and use singular value decomposition or structured total least squares approximation and Gauss–Newton optimization to numerically compute the approximate multivariate factors. We demonstrate on a large set of benchmark polynomials that our algorithms efficiently yield approximate factorizations within the coefficient noise even when the relative error in the input is substantial (10⁻³).     

A new algorithm for sparse interpolation of multivariate polynomials

To reconstruct a black box multivariate sparse polynomial from its floating point evaluations, the existing algorithms need to know upper bounds for both the number of terms in the polynomial and the partial degree in each of the variables. Here we present a new technique, based on Rutishauser’s qd$qd$-algorithm, in which we overcome both drawbacks.     

A new approach to linear regression with multivariate splines

A new methodology for creating highly accurate, static nonlinear maps from scattered, multivariate data is presented. This new methodology uses the B-form polynomials of multivariate simplex splines in a new linear regression scheme. This allows the use of standard parameter estimation techniques for estimating the B-coefficients of the multivariate simplex splines. We present a generalized least squares estimator for the B-coefficients, and show how the estimated B-coefficient variances lead to a new model quality assessment measure in the form of the B-coefficient variance surface. The new modeling methodology is demonstrated on a nonlinear scattered bivariate dataset.     

A factorization approach to evaluating simultaneous influence diagrams

Evaluating an influence diagram (ID) is a challenging problem because its complexity increases exponentially in the number of decision nodes in the diagram. In this paper, we examine the problem for a special class of IDs where multiple decisions must be made simultaneously. We describe a brief theory that factorizes out the computations common to all policies in evaluating them. Our evaluation approach conducts these computations once and uses them across all policies. We identify the ID structures for which the approach can achieve savings. We show that the approach can be used to efficiently recompute the optimal policy of an ID when its structure or parameters change. Finally, we demonstrate the superior performance of the approach by simulation studies and a military planning example.     

A symbolic approach to automatic multiword term structuring

This paper presents a three-level structuring of multiword terms basing on lexical inclusion, WordNet similarity and a clustering approach. Term clustering by automatic data analysis methods offers an interesting way of organizing a domain’s knowledge structure, useful for several information-oriented tasks like science and technology watch, textmining, computer-assisted ontology population, Question Answering (Q–A). This paper explores how this three-level term structuring brings to light the knowledge structures from a corpus of genomics and compares the mapping of the domain topics against a hand-built ontology (the GENIA ontology). Ways of integrating the results into a Q–A system are discussed.     

A symbolic summation approach to Feynman integral calculus

Given a Feynman parameter integral, depending on a single discrete variable N$N$ and a real parameter ε$\epsilon$, we discuss a new algorithmic framework to compute the first coefficients of its Laurent series expansion in ε$\epsilon$. In a first step, the integrals are expressed by hypergeometric multi-sums by means of symbolic transformations. Given this sum format, we develop new summation tools to extract the first coefficients of its series expansion whenever they are expressible in terms of indefinite nested product–sum expressions. In particular, we enhance the known multi-sum algorithms to derive recurrences for sums with complicated boundary conditions, and we present new algorithms to find formal Laurent series solutions of a given recurrence relation.     

On the synthetic factorization of projectively invariant polynomials

We prove that, after multiplication with a suitable monomial, every homogeneous bracket polynomial of rank r≥3 can be factored into a meet and join expression in the Cayley algebra. The main tool in our construction is an explicit algorithm for rewriting polynomial functions in terms of synthetic constructions in projective geometry. We also discuss applications of Cayley factorization to automated geometry theorem proving.     

A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor

We develop an algorithm for computing the symbolic Cholesky factorization of a large sparse symmetric positive definite matrix. The algorithm is intended for a message-passing multiprocessor system, such as the hypercube, and is based on the concept of elimination forest. In addition, we provide an algorithm for computing these forests along with a discussion of the algorithm's complexity and a proof of its correctness.     

Efficient evaluation of multivariate polynomials

In CAGD applications, the usual way to store a polynomial defined over a triangle is in the Bernstein-Bézier form, and the accepted way to evaluate it at a given point in the triangle is by the de Casteljau algorithm. In this paper we present an algorithm for evaluating Berstein-Bézier type polynomials which is significantly faster than de Casteljau. This suggests that a modified form of Bernstein-Bézier may be preferable for CAGD applications (as well as in applications of piecewise polynomials in data fitting and numerical solution of boundary-value problems).     

A new approach for multivariate data modelling in orthogonal geometry

Decomposing multivariate functions in terms of less variate components such as univariate or bivariate structures is an efficient way to reduce the mathematical and computational complexity of the related problem in computer-based applications. The enhanced multivariance product representation (EMPR) method is an extension to high-dimensional model representation (HDMR) which has a divide-and-conquer philosophy. The EMPR method has some additional structures named as support functions in its expansion when compared with HDMR and we have an important flexibility in selecting these support function structures. This selection process makes the method more successful than HDMR in most cases. In this sense, this work aims to apply the EMPR method to the multivariate data modelling problems having orthogonal geometries. The numerical results also show that the idea of this work is successfully applied to the considered problems and we obtain good representations in data modelling.     

A synergistic approach to improving symbolic execution using test ranges

Innovations in Systems and Software Engineering - Symbolic execution is a systematic technique for checking programs, which has received a lot of research attention during the last decade. In...     

Deterministic distinct-degree factorization of polynomials over finite fields

A deterministic polynomial time algorithm is presented for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving a theoretical open problem of Kaltofen from 1987.     

Semi-numerical absolute factorization of polynomials with integer coefficients

In this paper, we propose a semi-numerical algorithm for computing absolute factorization of multivariate polynomials. It is based on some properties appearing after a generic change of coordinate. Using numerical computation, Galois group action and rational approximation, this method provides an efficient probabilistic algorithm for medium degrees. Two implementations are presented and compared to other algorithms.     

Generalized Lyapunov equation and factorization of matrix polynomials

This paper presents an algorithm for the construction of a solution of the generalized Lyapunov equation. It is proved that the polynomial matrix factorization relative to the imaginary axis may be reduced to the successive solution of Lyapunov equations, i.e. the factorization is reduced to the solution of a sequence of generalized Lyapunov equations, not to the solution of generalized Riccati equation.     

A symbolic model checking approach to verifying satellite onboard software

This paper discusses the use of symbolic model checking technology to verify the design of an embedded satellite software control system called the attitude and orbit control system (AOCS). This system is mission critical because it is responsible for maintaining the attitude of the satellite and for performing fault detection, isolation, and recovery decisions. An executable AOCS implementation by Space Systems Finland has been provided in Ada source code form, and we use the input language of the symbolic model checker NuSMV 2 to model the implementation at a detailed level. We describe the modeling techniques and abstractions used to alleviate the state space explosion due to the handling of timers and the large number of system components controlled by the AOCS. The required behavior has been specified as extended state machine diagrams and translated to temporal logic properties. Besides well-known LTL and CTL model checking algorithms, we adapt a previously unexplored form of the liveness-to-safety approach to the problem. The latter new technique turns out to successfully prove all desired properties of the system, outperforming both the LTL and CTL implementations of NuSMV 2.     

A new approach for parameter identification of time-varying systems via generalized orthogonal polynomials

A very effective method of using the generalized orthogonal polynomials (GOP) for identifying the parameters of a process whose behaviour can be modelled by a linear differential equation with time-varying coefficients in the form of finite-order polynomials is presented. It is based on the differentiation operational matrix of the GOP, which can represent all kinds of individual orthogonal polynomials. The main advantage of using the differentiation operational matrix is that parameter estimation can be made starting at any time of interest, i.e. without the restriction of starting at zero time. In addition, the present computation algorithm is simpler than that of the integration operational matrix. Using the concept of GOP expansion for state and control functions, the differential input-output equation is converted into a set of linear algebraic equations. The unknown parameters are evaluated by a weighted least-squares estimation method. Very satisfactory results for illustrative example are obtained.     

Single-factor lifting and factorization of polynomials over local fields

Let f(x)$f\left(x\right)$ be a separable polynomial over a local field. The Montes algorithm computes certain approximations to the different irreducible factors of f(x)$f\left(x\right)$, with strong arithmetic properties. In this paper, we develop an algorithm to improve any one of these approximations, till a prescribed precision is attained. The most natural application of this “single-factor lifting” routine is to combine it with the Montes algorithm to provide a fast polynomial factorization algorithm. Moreover, the single-factor lifting algorithm may be applied as well to accelerate the computational resolution of several global arithmetic problems in which the improvement of an approximation to a single local irreducible factor of a polynomial is required.     

Bounds on absolute positiveness of multivariate polynomials

We propose and study a weighting framework for obtaining bounds on absolute positiveness of multivariate polynomials. It is shown that a well-known bound _BG$B_G$ by Hong is obtainable in this framework, and w.r.t. any bound in this framework _BG$B_G$ has a multiplicative overestimation which is at most linear in the number of variables. We also propose a general method to algorithmically improve any bound within the framework. In the univariate case, we derive the minimum number of weights necessary to obtain a bound with limited overestimation w.r.t. the absolute positiveness of the polynomial.