A combinatorial problem related to sparse systems of equations

Nowadays sparse systems of equations occur frequently in science and engineering. In this contribution we deal with sparse systems common in cryptanalysis. Given a cipher system, one converts it into a system of sparse equations, and then the system is solved to retrieve either a key or a plaintext. Raddum and Semaev proposed new methods for solving such sparse systems common in modern ciphers which are combinations of linear layers and small S-boxes. It turns out that the solution of a combinatorial MaxMinMax problem provides an upper bound on the average computational complexity of those methods. In this paper we initiate the study of a linear algebra variation of the MaxMinMax problem. The complexity bound proved in this paper significantly overcomes conjectured complexity bounds for Gröbner basis type algorithms.     

Spectral Theory of Differential Operators and Energy Levels of Subatomic Particles

Motivated by the Bohr atomic model, in this article we establish a mathematical theory to study energy levels, corresponding to bounds states, for subatomic particles. We show that the energy levels of each subatomic particle are finite and discrete, and corresponds to negative eigenvalues of the related eigenvalue problem. Consequently there are both upper and lower bounds of the energy levels for all subatomic particles. In particular, the energy level theory implies that the frequencies of mediators such as photons and gluons are also discrete and finite. Both the total number $N$ of energy levels and the average energy level gradient (for two adjacent energy levels) are rigorously estimated in terms of certain physical parameters. These estimates show that the energy level gradient is extremely small, consistent with the fact that it is hard to notice the discrete behavior of the frequency of subatomic particles.     

On the row merge tree for sparse LU factorization with partial pivoting

We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property. Our primary goal in this paper is to address the structure prediction problem for matrices satisfying a weaker assumption, which is the Hall property. For this we consider the row merge matrix, an upper bound that contains the nonzeros in L and U for all possible row permutations that can be performed during the numerical factorization with partial pivoting. We discuss the row merge tree, a structure that represents information obtained from the row merge matrix; that is, information on the dependencies among the columns in Gaussian elimination with partial pivoting and on structural upper bounds of the factors L and U. We present new theoretical results that show that the nonzero structure of the row merge matrix can be described in terms of branches and subtrees of the row merge tree. These results lead to an efficient algorithm for the computation of the row merge tree, that uses as input the structure of A, and has a time complexity almost linear in the number of nonzeros in A. We also investigate experimentally the usage of the row merge tree for structure prediction purposes on a set of matrices that satisfy only the Hall property. We analyze in particular the size of upper bounds of the structure of L and U, the reordering of the matrix based on a postorder traversal and its impact on the factorization runtime. We show experimentally that for some matrices, the row merge tree is a preferred alternative to the column elimination tree. AMS subject classification (2000)  65F50, 65F05, 68R10     

Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem

Recently, the first author introduced some cryptographic functions closely related to the Diffie-Hellman problem called P-Diffie-Hellman functions. We show that the existence of a low-degree polynomial representing a P-Diffie-Hellman function on a large set would lead to an efficient algorithm for solving the Diffie-Hellman problem. Motivated by this result we prove lower bounds on the degree of such interpolation polynomials. Analogously, we introduce a class of functions related to the discrete logarithm and show similar reduction and interpolation results.     

Hamiltonian index is NP-complete

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.     

Stability in geodesics for memoryless binary long-lived consensus

The determination of the stability of the long-lived consensus problem is a fundamental open problem in distributed systems. We concentrate on the memoryless binary case with geodesic paths. We offer a conjecture on the stability in this case, exhibit two classes of colourings which attain this conjectured bound, and improve the known lower bounds for all colourings. We also introduce a related parameter, which measures the stability only for certain geodesics, and for which we also prove lower bounds.     

Axial Compression of a Thin Elastic Cylinder: Bounds on the Minimum Energy Scaling Law

We consider the axial compression of a thin elastic cylinder placed about a hard cylindrical core. Treating the core as an obstacle, we prove upper and lower bounds on the minimum energy of the cylinder that depend on its relative thickness and the magnitude of axial compression. We focus exclusively on the setting where the radius of the core is greater than or equal to the natural radius of the cylinder. We consider two cases: the “large mandrel” case, where the radius of the core exceeds that of the cylinder, and the “neutral mandrel” case, where the radii of the core and cylinder are the same. In the large mandrel case, our upper and lower bounds match in their scaling with respect to thickness, compression, and the magnitude of pre‐strain induced by the core. We construct three types of axisymmetric wrinkling patterns whose energy scales as the minimum in different parameter regimes, corresponding to the presence of many wrinkles, few wrinkles, or no wrinkles at all. In the neutral mandrel case, our upper and lower bounds match in a certain regime in which the compression is small as compared to the thickness; in this regime, the minimum energy scales as that of the unbuckled configuration. We achieve these results for both the von Kármán–Donnell model and a geometrically nonlinear model of elasticity. © 2017 Wiley Periodicals, Inc.     

A new destructive bounding scheme for the bin packing problem

In this paper, we present a new lower bounding scheme for the one-dimensional bin packing problem based on a destructive approach and we prove its effectiveness to solve hard instances. Performance comparison to other available lower bounds shows the effectiveness of our proposed lower bounds.     

Blister Patterns and Energy Minimization in Compressed Thin Films on Compliant Substrates

This paper is motivated by the complex blister patterns sometimes seen in thin elastic films on thick, compliant substrates. These patterns are often induced by an elastic misfit that compresses the film. Blistering permits the film to expand locally, reducing the elastic energy of the system. It is therefore natural to ask: what is the minimum elastic energy achievable by blistering on a fixed area fraction of the substrate? This is a variational problem involving both the elastic deformation of the film and substrate and the geometry of the blistered region. It involves three small parameters: the nondimensionalized thickness of the film, the compliance ratio of the film/substrate pair, and the mismatch strain. In formulating the problem, we use a small‐slope (Föppl–von Kármán) approximation for the elastic energy of the film, and a local approximation for the elastic energy of the substrate. For a one‐dimensional version of the problem, we obtain “matching” upper and lower bounds on the minimum energy, in the sense that both bounds have the same scaling behavior with respect to the small parameters. The upper bound is straightforward and familiar: it is achieved by periodic blistering on a specific length scale. The lower bound is more subtle, since it must be proved without any assumption on the geometry of the blistered region. For a two‐dimensional version of the problem, our results are less complete. Our upper and lower bounds only “match” in their scaling with respect to the nondimensionalized thickness, not in the dependence on the compliance ratio and the mismatch strain. The lower bound is an easy consequence of our one‐dimensional analysis. The upper bound considers a two‐dimensional lattice of blisters and uses ideas from the literature on the folding or “crumpling” of a confined elastic sheet. Our main two‐dimensional result is that in a certain parameter regime, the elastic energy of this lattice is significantly lower than that of a few large blisters. © 2015 Wiley Periodicals, Inc.     

Sparse principal component analysis via regularized low rank matrix approximation

Principal component analysis (PCA) is a widely used tool for data analysis and dimension reduction in applications throughout science and engineering. However, the principal components (PCs) can sometimes be difficult to interpret, because they are linear combinations of all the original variables. To facilitate interpretation, sparse PCA produces modified PCs with sparse loadings, i.e. loadings with very few non-zero elements. In this paper, we propose a new sparse PCA method, namely sparse PCA via regularized SVD (sPCA-rSVD). We use the connection of PCA with singular value decomposition (SVD) of the data matrix and extract the PCs through solving a low rank matrix approximation problem. Regularization penalties are introduced to the corresponding minimization problem to promote sparsity in PC loadings. An efficient iterative algorithm is proposed for computation. Two tuning parameter selection methods are discussed. Some theoretical results are established to justify the use of sPCA-rSVD when only the data covariance matrix is available. In addition, we give a modified definition of variance explained by the sparse PCs. The sPCA-rSVD provides a uniform treatment of both classical multivariate data and high-dimension-low-sample-size (HDLSS) data. Further understanding of sPCA-rSVD and some existing alternatives is gained through simulation studies and real data examples, which suggests that sPCA-rSVD provides competitive results.     

A column generation approach for solving the patient admission scheduling problem

This paper addresses the Patient Admission Scheduling (PAS) problem. The PAS problem entails assigning elective patients to beds, while satisfying a number of hard constraints and as many soft constraints as is possible, and arises at all planning levels for hospital management. There exist a few, different variants of this problem. In this paper we consider one such variant and propose an optimization-based heuristic building on branch-and-bound, column generation, and dynamic constraint aggregation to solve it. We achieve tighter lower bounds than previously reported in the literature and, in addition, we are able to produce new best known solutions for five out of twelve instances from a publicly available repository.     

A geometric approach to divergent points of higher dimensional Collatz mappings

We define generalized Collatz mappings on free abelian groups of finite rank and study their iteration trajectories. Using geometric arguments we describe cones of points having a divergent trajectory and we deduce lower bounds for the density of the set of divergent points. As an application we give examples which show that the iteration of generalized Collatz mappings on rings of algebraic integers can behave quite differently from the conjectured behavior in \(\mathbb {Z}\).     

Spreading–vanishing dichotomy in a diffusive logistic model with a free boundary, II

We study the diffusive logistic equation with a free boundary in higher space dimensions and heterogeneous environment. Such a model may be used to describe the spreading of a new or invasive species, with the free boundary representing the expanding front. For simplicity, we assume that the environment and the solution are radially symmetric. In the special case of one space dimension and homogeneous environment, this free boundary problem was investigated in Du and Lin (2010) [10]. We prove that the spreading-vanishing dichotomy established in Du and Lin (2010) [10] still holds in the more general and ecologically realistic setting considered here. Moreover, when spreading occurs, we obtain best possible upper and lower bounds for the spreading speed of the expanding front. When the environment is asymptotically homogeneous at infinity, these two bounds coincide. Our results indicate that the asymptotic spreading speed determined by this model does not depend on the spatial dimension.     

Minimum energy configurations on a toric lattice as a quadratic assignment problem

We consider three known bounds for the quadratic assignment problem (QAP): an eigenvalue, a convex quadratic programming (CQP), and a semidefinite programming (SDP) bound. Since the last two bounds were not compared directly before, we prove that the SDP bound is stronger than the CQP bound. We then apply these to improve known bounds on a discrete energy minimization problem, reformulated as a QAP, which aims to minimize the potential energy between repulsive particles on a toric grid. Thus we are able to prove optimality for several configurations of particles and grid sizes, complementing earlier results by Bouman et al. (2013). The semidefinite programs in question are too large to solve without pre-processing, and we use a symmetry reduction method by Permenter and Parrilo (2020) to make computation of the SDP bounds possible.     

Randomized Simplex Algorithms on Klee-Minty Cubes

The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds (for the expected running time of the random-edge simplex algorithm on Klee-Minty cubes) conjectured in the literature. At the same time, we establish quadratic upper bounds for the expected length of a path for a simplex algorithm with random pivots on the classes of linear programs under investigation. In contrast to this, we find that the average length of an increasing path in a Klee-Minty cube is exponential when all paths are taken with equal probability. Received: September 2, 1996     

Products of foldable triangulations

Regular triangulations of products of lattice polytopes are constructed with the additional property that the dual graphs of the triangulations are bipartite. The (weighted) size difference of this bipartition is a lower bound for the number of real roots of certain sparse polynomial systems by recent results of Soprunova and Sottile [E. Soprunova, F. Sottile, Lower bounds for real solutions to sparse polynomial systems, Adv. Math. 204 (1) (2006) 116–151]. Special attention is paid to the cube case.     

Comparisons of weak regular splittings and multisplitting methods

Summary Comparison results for weak regular splittings of monotone matrices are derived. As an application we get upper and lower bounds for the convergence rate of iterative procedures based on multisplittings. This yields a very simple proof of results of Neumann-Plemmons on upper bounds, and establishes lower bounds, which has in special cases been conjectured by these authors.Dedicated to the memory of Peter Henrici     

Local Thermal Equilibrium States and Quantum Energy Inequalities

In this paper we investigate the energy distribution of states of a linear scalar quantum field with arbitrary curvature coupling on a curved spacetime which fulfill some local thermality condition. We find that this condition implies a quantum energy inequality for these states, where the (lower) energy bounds depend only on the local temperature distribution and are local and covariant (the dependence of the bounds other than on temperature is on parameters defining the quantum field model, and on local quantities constructed from the spacetime metric). Moreover, we also establish the averaged null energy condition (ANEC) for such locally thermal states, under growth conditions on their local temperature and under conditions on the free parameters entering the definition of the renormalized stress-energy tensor. These results hold for a range of curvature couplings including the cases of conformally coupled and minimally coupled scalar field. Submitted: February 27, 2008. Accepted: May 5, 2008.     

Sparse principal component analysis subject to prespecified cardinality of loadings

Most of the existing procedures for sparse principal component analysis (PCA) use a penalty function to obtain a sparse matrix of weights by which a data matrix is post-multiplied to produce PC scores. In this paper, we propose a new sparse PCA procedure which differs from the existing ones in two ways. First, the new procedure does not sparsify the weight matrix. Instead, the so-called loadings matrix is sparsified by which the score matrix is post-multiplied to approximate the data matrix. Second, the cardinality of the loading matrix i.e., the total number of nonzero loadings, is pre-specified to be an integer without using penalty functions. The procedure is called unpenalized sparse loading PCA (USLPCA). A desirable property of USLPCA is that the indices for the percentages of explained variances can be defined in the same form as in the standard PCA. We develop an alternate least squares algorithm for USLPCA which uses the fact that the PCA loss function can be decomposed as a sum of a term irrelevant to the loadings, and another one being easily minimized under cardinality constraints. A procedure is also presented for selecting the best cardinality using information criteria. The procedures are assessed in a simulation study and illustrated with real data examples.     

Static arbitrage bounds on basket option prices

We consider the problem of computing upper and lower bounds on the price of an European basket call option, given prices on other similar options. Although this problem is hard to solve exactly in the general case, we show that in some instances the upper and lower bounds can be computed via simple closed-form expressions, or linear programs. We also introduce an efficient linear programming relaxation of the general problem based on an integral transform interpretation of the call price function. We show that this relaxation is tight in some of the special cases examined before.