Search

We report on our on-going efforts to apply real quantifier elimination to the synthesis of optimal numerical algorithms. In particular, we describe a case study on the square root problem: given a real number x and an error bound ε , find a real interval such that it contains x and its width is less than or equal to ε . A typical numerical algorithm starts with an initial interval and repeatedly updates it by applying a “refinement map” on it until it becomes narrow enough. Thus the synthesis amounts to finding a refinement map that ensures the correctness and optimality of the resulting algorithm. This problem can be formulated as a real quantifier elimination. Hence, in principle, the synthesis can be carried out automatically. However, the computational requirement is huge, making the automatic synthesis practically impossible with the current general real quantifier elimination software. We overcame the difficulty by (1) carefully reducing a complicated quantified formula into several simpler ones and (2) automatically eliminating the quantifiers from the resulting ones using the state-of-the-art quantifier elimination software. As the result, we were able to synthesize semi-automatically an optimal quadratically 1 convergent map, which is better than the well known hand-crafted Secant-Newton map. Interestingly, the optimal synthesized map is not contracting as one would naturally expect. [ABSTRACT FROM AUTHOR]

Inferentialism claims that the rules for the use of an expression express its meaning without any need to invoke meanings or denotations for them. Logical inferentialism endorses inferentialism specifically for the logical constants. Harmonic inferentialism, as the term is introduced here, usually but not necessarily a subbranch of logical inferentialism, follows Gentzen in proposing that it is the introduction-rules which give expressions their meaning and the elimination-rules should accord harmoniously with the meaning so given. It is proposed here that the logical expressions are those which can be given schematic rules that lie in a specific sort of harmony, general-elimination (ge) harmony, resulting from applying a certain operation, the ge-procedure, to produce ge-rules in accord with the meaning defined by the I-rules. Griffiths (2014) claims that identity cannot be given such rules, concluding that logical inferentialists are committed to ruling identity a nonlogical expression. It is shown that the schematic rules for identity given in Read (2004), slightly amended, are indeed ge-harmonious, so confirming that identity is a logical notion. [ABSTRACT FROM AUTHOR]

We prove that if T is a complete theory with weak elimination of imaginaries, then there is an explicit bijection between strict independence relations for T and strict independence relations for Teq. We use this observation to show that if T is the theory of the Fraïssé limit of finite metric spaces with integer distances, then Teq has more than one strict independence relation. This answers a question of Adler (J Math Log 9(1):1-20, , Question 1.7). [ABSTRACT FROM AUTHOR]

The $$\Omega $$ -rule was introduced by W. Buchholz to give an ordinal-free proof of cut-elimination for a subsystem of analysis with $$\Pi ^{1}_{1}$$ -comprehension. W. Buchholz's proof provides cut-free derivations by familiar rules only for arithmetical sequents. When second-order quantifiers are present, they are introduced by the $$\Omega $$ -rule and some residual cuts are not eliminated. In the present paper, we introduce an extension of the $$\Omega $$ -rule and prove the complete cut-elimination by the same method as W. Buchholz: any derivation of arbitrary sequent is transformed into its cut-free derivation by the standard rules (with induction replaced by the $$\omega $$ -rule). In fact we treat the subsystem of $$\Pi ^{1}_{1}$$ -CA (of the same strength as $$ID_{1}$$ ) that W. Buchholz used for his explanation of G. Takeuti's finite reductions. Extension to full $$\Pi ^{1}_{1}$$ -CA is planned for another paper. [ABSTRACT FROM AUTHOR]

Motivated by a recent Basu–Martin–Ryan paper, we obtain a reduced primal-dual pair of a linear semi-infinite programming problem by applying an amended Fourier–Motzkin elimination method to the linear semi-infinite inequality system. The reduced primal-dual pair is equivalent to the original one in terms of consistency, optimal values and asymptotic consistency. Working with this reduced pair and reformulating a linear semi-infinite programme as a linear programme over a convex cone, we reproduce all the theorems that lead to the full eleven possible duality state classification theory. Establishing classification results with the Fourier–Motzkin method means that the two classification theorems for linear semi-infinite programming, 1969 and 1974, have been proved by new and exciting methods. We also show in this paper that the approach to study linear semi-infinite programming using Fourier–Motzkin elimination is not purely algebraic, it is mixed algebraic-analysis. [ABSTRACT FROM AUTHOR]

A number of philosophers think that grounding is, in some sense, well-founded. This thesis, however, is not always articulated precisely, nor is there a consensus in the literature as to how it should be characterized. In what follows, I consider several principles that one might have in mind when asserting that grounding is well-founded, and I argue that one of these principles, which I call 'full foundations', best captures the relevant claim. My argument is by the process of elimination. For each of the inadequate principles, I illustrate its inadequacy by showing either that it excludes cases that should not be ruled out by a well-foundedness axiom for grounding, or that it admits cases that should be ruled out. [ABSTRACT FROM AUTHOR]

This study compared four lineup procedures: the simultaneous, sequential, elimination, and wildcard. Two hundred and sixty-nine university students ( M = 20.17 years) watched a mock, videotaped crime. Then, following a brief delay, they viewed a 6-person target-present or -absent lineup using one of the four lineup procedures. For target-present lineups, correct identification rates for the four lineup procedures were comparable. In contrast, for target-absent lineups, the correct rejection rate was higher using the elimination lineup procedure compared to the wildcard and simultaneous lineup procedures. Remaining comparisons between lineup procedures found no significant differences. Also diagnosticity ratios were similar across the four procedures. [ABSTRACT FROM AUTHOR]

A method for eliminating residual vibrations in multimode systems is presented using a command shaping technique. The proposed command shaping technique captures two main advantages. Namely, the independence of the time length of the shaped command from the resonant frequencies of the system, and the ability to generate the command profile without a full system model. Experiments on systems with partial models represented by their resonant frequencies show that shaped command profiles generated using actual measured resonant frequencies of a system outperform those based on mathematical models. This feature of the proposed command shaping technique makes it very attractive for complicated multimode systems where mathematical models are difficult to build. Profiles of the proposed shaped command are simple and do not require intensive calculations. Performance of the proposed shaped command is validated using numerical simulations and experiments. Numerical simulations prove that the shaped commands are capable of completely eliminating residual vibrations of multimode systems. Experiments show that residual vibration elimination depends on the level of accuracy of the measured resonant frequencies of the system. [ABSTRACT FROM AUTHOR]

The ADC method of proof search in propositional natural deduction proposed in 2000 proceeds bottom up first by Analysing the sequent into sub-goals by applying all possible introduction rules, and then by checking whether each of these sub-goals can be established using only elimination rules (Direct Chaining). This looks simpler than the worst case complexity (PSPACE) of the derivability problem for intuitionistic propositional logic.We investigate the complexity ofADC for various fragments. ADC derivability is polynomially decidable for the &,→-fragment by a generalization of a familiar direct chaining algorithm for Horn formulas. Adding ⋁ leads to a CoNP-complete fragment. A short counterexample in case the goal sequent is not ADC derivable is provided by witnessing all relevant disjunctions. Adding constant ⊥ preserves CoNP completeness. [ABSTRACT FROM AUTHOR]

The sports elimination problem asks whether a team participating in a competition still has a chance to win, given the current standings and the remaining matches to be played among the teams. This problem can be viewed as a graph labelling problem, where arcs receive labels that contribute to the score of both endpoints of the arc, and the aim is to label the arcs in a way that each vertex obtains a score not exceeding its capacity. We investigate the complexity of this problem in detail, using a multivariate approach to examine how various parameters of the input graph (such as the maximum degree, the feedback vertex/edge number, and different width parameters) influence the computational tractability. We obtain several efficient algorithms, as well as certain hardness results. [ABSTRACT FROM AUTHOR]

While tools from structural graph theory such as tree- or path-width have proved to be highly successful in coping with computational intractability on undirected graphs, corresponding width measures for directed graphs have not yet fulfilled their promise for broad algorithmic applications on directed graphs. One reason for this is that in most existing digraph width measures the class of acyclic digraphs has small width which immediately implies hardness of problems such as computing directed dominating sets. Fernau and Meister (2014) introduce the concept of elimination width and a corresponding graph searching game which overcomes this problem with acyclic digraphs. In their paper, the focus was on structural characterizations of classes of digraphs of bounded elimination width. In this paper we study elimination width from an algorithmic and graph searching perspective. We analyse variations of the elimination width game and show that this leads to width measures on which the directed dominating set problem and some variants of it become tractable. [ABSTRACT FROM AUTHOR]

Solvers for linear systems with tridiagonal coefficient matrices sometimes employ direct methods such as the Gauss elimination method or the cyclic reduction method. In each step of the cyclic reduction method, nonzero offdiagonal entries in the coefficient matrix move incrementally away from diagonal entries and eventually vanish. The steps of the cyclic reduction method are generalized as forms of the stride reduction method. For example, the 2-stride reduction method coincides with the 1st step of the cyclic reduction method which transforms tridiagonal linear systems into pentadiagonal systems. In this paper, we explain arbitrary-stride reduction for linear systems with coefficient matrices with three nonzero bands. We then show that arbitrary-stride reduction is equivalent to a combination of 2-stride reduction and row and column permutations. We thus clarify eigenvalue clustering of coefficient matrices in the step-by-step process of the stride reduction method. We also provide two examples verifying this property. [ABSTRACT FROM AUTHOR]

Classifying large and real-world datasets is a challenging problem in machine learning algorithms. Among the machine learning methods, the support vector machine (SVM) is a well-known approach with high generalization ability. Unfortunately, while the number of training data increases and the data contain noise, the performance of SVM signifcantly decreases. In this paper, a fast and de-noise two-stage method for training SVMs to deal with large, real- world datasets is proposed. In the frst stage, data that contain noises or are suspected to be noisy are identifed and eliminated from the genuine training dataset. The process of elimination and identifcation is based on the movement of the center of the convex hull data in the training dataset. The convex hull data are computed via the QHull algorithm. On the other hand, the well-known fuzzy clustering method (FCM) is applied to compress and reduce the size of the training dataset. Finally, the reduced and purifed cluster centers are used for training the SVM. A set of experiments is conducted on the four benchmarking datasets of the UCI database. Moreover, the amount of training time and the generalization of the proposed approach are compared with FCM-SVM and normal SVM. The results indicate that the proposed method reduces the amount of training time and has a considerable success in removing noisy data from the training dataset. Therefore, the proposed method can achieve a higher generalization performance in comparison with the other methods in large, real-world datasets. [ABSTRACT FROM AUTHOR]

This paper proposes an unambiguous correlation function applicable to generic sine-phased binary offset carrier (BOC) signal tracking. In the proposed scheme, first, we view the BOC sub-carrier pulse as a sum of multiple rectangular pulses. Then, we obtain partial correlation functions by correlating the multiple rectangular pulses with the received signal, and subsequently, construct two symmetric correlation functions by combining the partial correlation functions in a specialized way. Finally, we generate an unambiguous correlation function by combining the two symmetric correlation functions. The proposed correlation function has a sharper main-peak, and consequently, provides a better tracking performance than those of the conventional correlation functions in terms of the tracking error standard deviation (TESD). [ABSTRACT FROM AUTHOR]

We define a reasonably well-behaved class of ultraimaginaries, i.e. classes modulo -invariant equivalence relations, called tame, and establish some basic simplicity-theoretic facts. We also show feeble elimination of supersimple ultraimaginaries: If is an ultraimaginary definable over a tuple with , then is eliminable up to rank . Finally, we prove some uniform versions of the weak canonical base property. [ABSTRACT FROM AUTHOR]

The inaccuracy and delay of speed feedback cause a vibration problem when the permanent magnet synchronous motor runs at low speed. As the low-speed smoothness is a key point of many applications of the permanent magnet synchronous motor, this article solves this problem by adding a real-time adjusted extended Kalman filter to low-precision-sensor vector control. In the mathematical model, the estimated speed of the extended kalman filter is significantly impacted by the deviations of the resistance and magnetic flux rather than other parameters. Thus, underid= 0 vector control, aRs-ψf-identifier is designed to calculate the values of the resistance and flux simultaneously with a small compensatingid. This algorithm runs on the platform in real time. Finally, the experiment results validate that when the velocity reaches as low as 1 r/min, the proposed method eliminates the vibration problem in the low-precision-sensor permanent magnet synchronous motor. [ABSTRACT FROM PUBLISHER]

Nuisance parameter elimination is a central problem in capture–recapture modelling. In this paper, we consider a closed population capture–recapture model which assumes the capture probabilities varies only with the sampling occasions. In this model, the capture probabilities are regarded as nuisance parameters and the unknown number of individuals is the parameter of interest. In order to eliminate the nuisance parameters, the likelihood function is integrated with respect to a weight function (uniform and Jeffrey's) of the nuisance parameters resulting in an integrated likelihood function depending only on the population size. For these integrated likelihood functions, analytical expressions for the maximum likelihood estimates are obtained and it is proved that they are always finite and unique. Variance estimates of the proposed estimators are obtained via a parametric bootstrap resampling procedure. The proposed methods are illustrated on a real data set and their frequentist properties are assessed by means of a simulation study. [ABSTRACT FROM AUTHOR]

Computers play a serious role in human life, especially web-based applications running twenty four hours per day. These applications are based on relational database management system and they receive many queries from the users. These queries are executed in the commercial systems one by one without any consideration of past experiences and data analysis. The execution of queries can be faster if some rules were derived from the past queries. In this paper, we propose a statistical query-based rule derivation system by the backward elimination algorithm, which analysis the data based on the past queries in order to derive new rules, and then it uses these rules for the execution of new queries. The computational results are presented and analysed that the system is very efficient and promising. [ABSTRACT FROM AUTHOR]

We generalize and unify various tools from the study of valued fields equipped with an automorphism to obtain a relative quantifier elimination result for such fields. Along the way we point how the techniques we employ relate to a classical result from tropical geometry. The quantifier elimination result we provide is then applied to the transseries field equipped with the automorphism which sends $$f(x)$$ to $$f(x+1)$$ . [ABSTRACT FROM AUTHOR]

We investigate incomplete symbols, i.e. definite descriptions with scope-operators. Russell famously introduced definite descriptions by contextual definitions; in this article definite descriptions are introduced by rules in a specific calculus that is very well suited for proof-theoretic investigations. That is to say, the phrase 'incomplete symbols' is formally interpreted as to the existence of an elimination procedure. The last section offers semantical tools for interpreting the phrase 'no meaning in isolation' in a formal way. [ABSTRACT FROM AUTHOR]

Underwater acoustic communications have found a growing interest because of its variety usages both in military and commercial applications. But, for ocean environment, the channel has an extended time varying multipath due to acoustic propagation. These phenomena cause pulse spreading and time varying inter-symbol interference (ISI). To overcome the interference caused by this harsh environment, equalizers with Passive Phase Conjugation (PPC) have been widely used in coherent communications. In this paper, we have proposed a combined scheme of PPC followed by an iteratively ISI cancelation algorithm to remove the residual ISI remained at the output of the PPC processor. By using a coarse estimation of the channel along with the ISI alleviated PPC output symbols; we can eliminate residual ISI from the received data signal. We have conducted extensive simulations and some experimental tests at the coastal environment of the Persian Gulf to investigate the performance of the proposed scheme. The advantages of the proposed combined scheme are using the channel probe signal for both frame synchronization and coarse estimation of the channel impulse response to using it in the iteratively ISI cancellation and the PPC processing block. The results showed the effectiveness of the combined method. [ABSTRACT FROM AUTHOR]

Fingerprint positioning can take advantage of existing WLAN to achieve indoor locations, which has been widely studied. We analyzed the corresponding positions distribution of similar fingerprints, and then found that the fuzzy similarity between fingerprints is the root cause of the larger errors existing. According to clusters distribution feature of corresponding positions of the similar fingerprints, we proposed a K-Means+ clustering algorithm to achieve fine-grained fingerprint positioning. Due to the K-Means+ algorithm failing to locate the positions of outliers, we also designed a linear sequence matching algorithm to improve the outliers positioning, and reduce the impact of fuzzy similarity. Experimental results illustrate that our algorithm can get a maximum positioning error less than 5 m, which outperforms other algorithms. Meanwhile, all the positioning errors over 4 m in our algorithm are less than 2%. The positioning accuracy has been improved significantly. [ABSTRACT FROM AUTHOR]

Given a rational projective parametrization P(s, t, v) of a rational projective surface S we present an algorithm such that, with the exception of a finite set (maybe empty) B of projective base points of P, decomposes the projective parameter plane as P2(K) \ B = Ulk=1 бk such that, if (s0 : t0 : v0) ∊ бk, then P(s0, t0, v0) is a point of S of multiplicity k. [ABSTRACT FROM AUTHOR]

For efficiency in a linear algebra course the instructor may wish to avoid the undue arithmetical distractions of rational arithmetic. In this paper we explore how to write fraction-free problems of various types including elimination, matrix inverses, orthogonality, and the (non-normalizing) Gram–Schmidt process. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of finding time-optimal trajectories in two-dimensional space, where the mover's speed monotonically decreases or increases in one of the space's coordinates. We address such problems in different settings for the velocity function and in the presence of obstacles. First, we consider the problem without any obstacles. We show that the problem with linear speed decrease is reducible to the de l'Hôpital's problem, and that, for this case, the time-optimal trajectory is a circular segment. Next, we show that the problem with linear speed decreases and rectilinear obstacles can be solved in polynomial time by a dynamic program. Finally, we consider the case without obstacles, where the medium is non-uniform and the mover's velocity is a piecewise linear function. We reduce this problem to that of solving a system of polynomial equations of fixed degree, for which algebraic elimination theory allows us to solve the problem to optimality. [ABSTRACT FROM AUTHOR]

Vertex elimination is a graph operation that turns the neighborhood of a vertex into a clique and removes the vertex itself. It has widely known applications within sparse matrix computations. We define the Elimination problem as follows: given two graphs G and H, decide whether H can be obtained from G by | V( G)|−| V( H)| vertex eliminations. We show that Elimination is $\mathsf {W[1]} $-hard when parameterized by | V( H)|, even if both input graphs are split graphs, and $\mathsf {W[2]} $-hard when parameterized by | V( G)|−| V( H)|, even if H is a complete graph. On the positive side, we show that Elimination admits a kernel with at most 5| V( H)| vertices in the case when G is connected and H is a complete graph, which is in sharp contrast to the $\mathsf {W[1]} $-hardness of the related Clique problem. We also study the case when either G or H is tree. The computational complexity of the problem depends on which graph is assumed to be a tree: we show that Elimination can be solved in polynomial time when H is a tree, whereas it remains NP-complete when G is a tree. [ABSTRACT FROM AUTHOR]

Given the equations of the first and the second order manifolds in R n , we construct the distance equation , i.e. a univariate algebraic equation one of the zeros of which (generically minimal positive) coincides with the square of the distance between these manifolds. To achieve this goal we employ Elimination Theory methods. In the frame of this approach we also deduce the necessary and sufficient algebraic conditions under which the manifolds intersect and propose an algorithm for finding the coordinates of their nearest points. The case of parameter dependent manifolds is also considered. [ABSTRACT FROM AUTHOR]

Quantifier elimination is a foundational issue in the field of algebraic and logic computation. In first-order logic, every formula is well composed of atomic formulas by negation, conjunction, disjunction, and introducing quantifiers. It is often made quite complicated by the occurrences of quantifiers and nonlinear functions in atomic formulas. In this paper, we study a class of quantified exponential polynomial formulas extending polynomial ones, which allows the exponential to appear in the first variable. We then design a quantifier elimination procedure for these formulas. It adopts the scheme of cylindrical decomposition that consists of four phases—projection, isolation, lifting, and solution formula construction. For the non-algebraic representation, the triangular systems are introduced to define transcendental coordinates of sample points. Based on that, our cylindrical decomposition produces projections for input variables only. Hence the procedure is direct and effective. [ABSTRACT FROM AUTHOR]

Elimination by aspects (EBA) is a random utility model that is considered to represent the choice process used by consumers more faithfully than logit and probit models. One limitation of the model is that it does not have a known error theory. We show that EBA can be derived by assuming that aspects have random utilities with independent, extreme value distributions. Multinomial logit and rank-ordered logit models are special cases of EBA. [ABSTRACT FROM AUTHOR]

We present a Poisson formula for sparse resultants and a formula for the product of the roots of a family of Laurent polynomials, which are valid for arbitrary families of supports. To obtain these formulae, we show that the sparse resultant associated to a family of supports can be identified with the resultant of a suitable multiprojective toric cycle in the sense of R'emond. This connection allows to study sparse resultants using multiprojective elimination theory and intersection theory of toric varieties. [ABSTRACT FROM AUTHOR]

A real matrix A = ( a i j ) 1 ≤ i , j , ≤ n is said to be almost strictly totally negative if it is almost strictly sign regular with signature ε = ( − 1 , − 1 , … , − 1 ) , which is equivalent to the property that all its nontrivial minors are negative. In this paper an algorithmic characterization of nonsingular almost strictly totally negative matrices is presented. [ABSTRACT FROM AUTHOR]

An algorithmic characterization of the nonsingular almost strictly sign regular matrices by Neville elimination is presented. [ABSTRACT FROM AUTHOR]

The strand symmetric model is a phylogenetic model designed to re ect the symmetry inherent in the double-stranded structure of DNA. We show that the set of known phylogenetic invariants for the general strand symmetric model of the three leaf claw tree entirely defines the ideal. This knowledge allows one to determine the vanishing ideal of the general strand symmetric model of any trivalent tree. Our proof of the main result is computational. We use the fact that the Zariski closure of the strand symmetric model is the secant variety of a toric variety to compute the dimension of the variety. We then show that the known equations generate a prime ideal of the correct dimension using elimination theory. [ABSTRACT FROM AUTHOR]

This paper deals with the computational modeling and numerical simulation of contact problems at finite deformations using the finite element method. Quasi-static and dynamic problems are considered and two particular frictional conditions, full stick friction and frictionless cases, are addressed. Lagrange multipliers and regularized formulations of the contact problem, such as penalty or augmented Lagrangian methods, are avoided and a new direct elimination method is proposed. Conserving algorithms are also introduced for the proposed formulation for dynamic contact problems. An assessment of the performance of the resulting formulation is shown in a number of selected benchmark tests and numerical examples, including both quasi-static and dynamic contact problems under full stick friction and frictionless contact conditions. Conservation of key discrete properties exhibited by the time stepping algorithm used for dynamic contact problems is also shown in an example. [ABSTRACT FROM AUTHOR]

We present an elimination theory-based method for solving equality-constrained multivariable polynomial least-squares problems in system identification. While most algorithms in elimination theory rely upon Groebner bases and symbolic multivariable polynomial division algorithms, we present an algorithm which is based on computing the nullspace of a large sparse matrix and the zeros of a scalar, univariate polynomial. [ABSTRACT FROM AUTHOR]

Connexive logic contains propositional theses such as NCpNp and CCpqNCpNq that are false in two-valued logic. It derives from remarks made by Sextus Empiricus in the fourth century B.C. The logic of causal and subjunctive conditionals is also connexive, since ‘If X is dropped, it will hit the floor’ contradicts ‘If X is dropped, it will not hit the floor’. In the paper below, a Gentzen Sequenzenkalkul formulation of connexive logic is constructed, and a proof is given of the elimination theorem. [ABSTRACT FROM AUTHOR]

The rigidity of a matrix A for target rank r is the minimum number of entries of A that must be changed to ensure that the rank of the altered matrix is at most r. Since its introduction by Valiant (), rigidity and similar rank-robustness functions of matrices have found numerous applications in circuit complexity, communication complexity, and learning complexity. Almost all n × n matrices over an infinite field have a rigidity of ( n − r). It is a long-standing open question to construct infinite families of explicit matrices even with superlinear rigidity when r = Ω( n). In this paper, we construct an infinite family of complex matrices with the largest possible, i.e., ( n − r), rigidity. The entries of an n × n matrix in this family are distinct primitive roots of unity of orders roughly exp( n log n). To the best of our knowledge, this is the first family of concrete (but not entirely explicit) matrices having maximal rigidity and a succinct algebraic description. Our construction is based on elimination theory of polynomial ideals. In particular, we use results on the existence of polynomials in elimination ideals with effective degree upper bounds (effective Nullstellensatz). Using elementary algebraic geometry, we prove that the dimension of the affine variety of matrices of rigidity at most k is exactly n - ( n - r) + k. Finally, we use elimination theory to examine whether the rigidity function is semicontinuous. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm called “volume & neighbors” for finding elimination trees for multifrontal solver algorithm applied to three dimensional h -adaptive finite element method computations. The algorithm is described in a pseudo-code and explained on exemplary h -refined grids. The algorithm is implemented in three dimensional h -adaptive finite element method code and tested on a sequence of representative grids, namely uniform grid, grid with point singularity, grid with edge singularity and grid with face singularity. The number of floating point operations for the multifrontal solver algorithm working with the elimination trees generated by the volume & neighbors algorithm is compared with the number of floating-point operations resulting from execution of the state-of-the-art multifrontal direct solver MUMPS with state-of-the-art algorithms for constructing elimination trees like nested-dissection from METIS library and approximate minimum degree AMD algorithm as well as PORD algorithm. In all the cases the volume & neighbors algorithm outperforms other state-of-the art algorithms. The only exception is the case of the uniform grid, where the algorithm results in a similar number of FLOPs than nested dissection algorithm. [ABSTRACT FROM AUTHOR]

Nonnegative tensor factorization has applications in statistics, computer vision, exploratory multiway data analysis, and blind source separation. A symmetric nonnegative tensor, which has an exact symmetric nonnegative factorization, is called a completely positive tensor. This concept extends the concept of completely positive matrices. A classical result in the theory of completely positive matrices is that a symmetric, diagonally dominated nonnegative matrix is a completely positive matrix. In this paper, we introduce strongly symmetric tensors and show that a symmetric tensor has a symmetric binary decomposition if and only if it is strongly symmetric. Then we show that a strongly symmetric, hierarchically dominated nonnegative tensor is a completely positive tensor, and present a hierarchical elimination algorithm for checking this. Numerical examples are given to illustrate this. Some other properties of completely positive tensors are discussed. In particular, we show that the completely positive tensor cone and the co-positive tensor cone of the same order are dual to each other. [ABSTRACT FROM AUTHOR]