A note on the linearity of Ratliff and Rosenthal's algorithm for optimal picker routing

Ratliff and Rosenthal state that their dynamic programming algorithm for optimal picker routing has linear complexity in the number of aisles. Indeed, solving the dynamic program is linear, but computing the cost coefficients of the dynamic program certainly requires the consideration of all picking positions, whose number is independent of the number of aisles. For a given unsorted sequence of picking positions, our algorithm is linear in the sum of the number of aisles and number of picking positions.     

On the outcome of false images of linear <Emphasis Type="Italic">k</Emphasis>-valued functions for composite numbers <Emphasis Type="Italic">k</Emphasis> when the number of variables increases

The problem of constructing discrete functions such that parts of their value sets determine (generate) arbitrary linear functions is considered. A case in which k is a prime number was considered earlier by the author. It is proved that the existence of such partial functions wshen the number of independent variables is no less then two implies they exists for any arbitrary greater number of independent variables. Upper estimates linear with respect to the number of independent variables are proved for the size of the domain of universal functions. The existence of two-variable universal functions is proved for sufficiently large k.     

Essential spectrum of singular discrete linear Hamiltonian systems

The paper is concerned with the essential spectral points of singular discrete linear Hamiltonian systems. Several sufficient conditions for a real point to be in the essential spectrum are obtained in terms of the number of linearly independent square‐summable solutions of the corresponding homogeneous linear system, and a sufficient and necessary condition for a real point to be in the essential spectrum is given in terms of the number of linearly independent square‐summable solutions of the corresponding nonhomogeneous linear system. As a direct consequence, the corresponding results for singular higher‐order symmetric vector difference expressions are given.     

亚纯系数齐次线性微分方程解的性质

本文研究了慢增长亚纯系数齐次线性微分方程亚纯解的零点收敛指数,得到了这类方程的线性无关超越解的最少个数和零点收敛指数为有穷的解的最多个数。     

Overlapping Schwarz Waveform Relaxation for the Heat Equation in N Dimensions

We analyze overlapping Schwarz waveform relaxation for the heat equation in n spatial dimensions. We prove linear convergence of the algorithm on unbounded time intervals and superlinear convergence on bounded time intervals. In both cases the convergence rates are shown to depend on the size of the overlap. The linear convergence result depends also on the number of subdomains because it is limited by the classical steady state result of overlapping Schwarz for elliptic problems. However the superlinear convergence result is independent of the number of subdomains. Thus overlapping Schwarz waveform relaxation does not need a coarse space for robust convergence independent of the number of subdomains, if the algorithm is in the superlinear convergence regime. Numerical experiments confirm our analysis. We also briefly describe how our results can be extended to more general parabolic problems.     

A note on reduction of the number of parameters in linear statistical models

In certain settings the mean response is modeled by a linear model using a large number of parameters. Sometimes it is desirable to reduce the number of parameters prior to conducting the experiment and prior to the actual statistical analysis. Essentially, it means to formulate a simpler approximate model to the original “ideal” one. The goal is to find conditions (on the model matrix and covariance matrix) under which the reduction does not influence essentially the data fit. Here we try to develop such conditions in regular linear model without and with linear restraints. We emphasize that these conditions are independent of observed data.     

Remarks on the spectrum of Dirac operators

This paper concerns the number of eigenvalues of the Dirac operator in ]-1,1[ and gives the number of linear independent eigenfunctions with total angular momentum k in [, 1[.     

The order of a zero of a Wronskian and the theory of linear dependence

Every root of the top Wronskian of a Wronskian matrix whose rank at the root is equal to the number of columns, is of integer order even if the highest derivatives exist only at the root. If the rank of a Wronskian matrix is constant and smaller than the number of rows, then the number of independent linear relations between the functions in the first row is equal to the number of functions minus the rank. These results were proved under additional assumptions by Bôcher, Curtiss, and Moszner. Their proofs are simplified.     

预报因子选择的条件数方法及其在台风强度预报中的应用

选择合适的变量是建立多元线性回归方程的重要问题.以减弱诸多变量之间的复共线性为目标,采用条件数分析方法选择多元回归模型的自变量.最后以西北太平洋海域2001-2011年5-7月的台风强度为研究对象,利用条件数方法建立预报方程进行预报试验,并进一步将该预报方法与逐步回归方法进行对比分析.     

Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm

In a recent paper Tardos described a polynomial algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In this paper we extend Tardos' results and present a polynomial algorithm for solving strictly convex quadratic programming problems in which the number of arithmetic steps is independent of the size of the numbers in the right hand side and the linear cost coefficients.This research was partially supported by the Natural Sciences and Engineering Research Council of Canada Grant 5-83998.     

Empirical likelihood test for high dimensional linear models

We propose an empirical likelihood method to test whether the coefficients in a possibly high-dimensional linear model are equal to given values. The asymptotic distribution of the test statistic is independent of the number of covariates in the linear model.     

Existence of dichotomies and invariant splittings for linear differential systems IV

The structure of linear skew-product dynamical systems is investigated in the case in which bounded orbits are admitted. The spectral decomposition theorem is applied and estimates are obtained giving lower bounds on the number of independent bounded solutions of a time varying linear ordinary differential system based on the limiting behavior of the system. The results are also used to study the stability behavior of a class of linear difference systems.     

The gap phenomenon in the dimension study of finite type systems

Several examples of gaps (lacunes) between dimensions of maximal and submaximal symmetric models are considered, which include investigation of number of independent linear and quadratic integrals of metrics and counting the symmetries of geometric structures and differential equations. A general result clarifying this effect in the case when the structure is associated to a vector distribution, is proposed.     

On the absence of global solutions to the gauss equation and solutions in external areas

We consider conditions under which the Gauss equation has no solutions defined in the whole space or in areas external with respect to a ball. The absence of solutions in external areas is established in the case when the number of independent variables is more than two. In the two-dimensional case we obtain conditions ensuring the absence of global solutions to the second-order elliptic equation with variable coefficients in its linear part.     

Boundary value problem for a second-order elliptic equation in the exterior of an ellipse

We consider a boundary value problem for a second-order linear elliptic differential equation with constant coefficients in a domain that is the exterior of an ellipse. The boundary conditions of the problem contain the values of the function itself and its normal derivative. We give a constructive solution of the problem and find the number of solvability conditions for the inhomogeneous problem as well as the number of linearly independent solutions of the homogeneous problem. We prove the boundary uniqueness theorem for the solutions of this equation.     

Bifurcation of solutions of singular Fredholm boundary value problems

We obtain conditions for the bifurcation of solutions of linear singular Fredholm boundary value problems with a small parameter under the assumption that the unperturbed singular differential system can be reduced to central canonical form. Using the Vishik-Lyusternik method and the technique of Moore-Penrose pseudoinverse matrices, we suggest an algorithm for finding a family of linearly independent solutions of such boundary value problems for the general case in which the number of boundary conditions specified by a linear vector functional does not coincide with the number of unknowns in the singular differential system.     

Some Properties for Analysis-Suitable $T$-Splines

Analysis-suitable $T$-splines (AS $T$-splines) are a mildly topological restricted subset of T-splines which are linear independent regardless of knot values [1–3]. The present paper provides some more iso-geometric analysis (IGA) oriented properties for AS $T$-splines and generalizes them to arbitrary topology AS $T$-splines. First, we prove that the blending functions for analysis-suitable T-splines are locally linear independent, which is the key property for localized multi-resolution and linear independence for non-tensor-product domain. And then, we prove that the number of $T$-spline control points which contribute each Bézier element is optimal, which is very important to obtain a bound for the number of non zero entries in the mass and stiffness matrices for IGA with $T$-splines. Moreover, it is found that the elegant labeling tool for B-splines, blossom, can also be applied for analysis-suitable $T$-splines.     

Criteria and dimension reduction of linear multiple criteria optimization problems

Two of the main approaches in multiple criteria optimization are optimization over the efficient set and utility function program. These are nonconvex optimization problems in which local optima can be different from global optima. Existing global optimization methods for solving such problems can only work well for problems of moderate dimensions. In this article, we propose some ways to reduce the number of criteria and the dimension of a linear multiple criteria optimization problem. By the concept of so-called representative and extreme criteria, which is motivated by the concept of redundant (or nonessential) objective functions of Gal and Leberling, we can reduce the number of criteria without altering the set of efficient solutions. Furthermore, by using linear independent criteria, the linear multiple criteria optimization problem under consideration can be transformed into an equivalent linear multiple criteria optimization problem in the space of linear independent criteria. This equivalence is understood in a sense that efficient solutions of each problem can be derived from efficient solutions of the other by some affine transformation. As a result, such criteria and dimension reduction techniques could help to increase the efficiency of existing algorithms and to develop new methods for handling global optimization problems arisen from multiple objective optimization.     

The construction of some efficient preconditioners in the boundary element method

The discretization of first kind boundary integral equations leads in general to a dense system of linear equations, whose spectral condition number depends on the discretization used. Here we describe a general preconditioning technique based on a boundary integral operator of opposite order. The corresponding spectral equivalence inequalities are independent of the special discretization used, i.e., independent of the triangulations and of the trial functions. Since the proposed preconditioning form involves a (pseudo)inverse operator, one needs for its discretization only a stability condition for obtaining a spectrally equivalent approximation. This revised version was published online in June 2006 with corrections to the Cover Date.