On systems of bilinear forms whose minimal division-free algorithms are all bilinear

In this paper we prove that for a certain class of systems of bilinear forms, all minimal division-free algorithms are essentially bilinear. This class includes systems for computing products in finite algebraic extension fields, and systems for computing the products of Toeplitz and Hankel matrices with vectors. Our results, together with the classification theorems of 10., 12., 169–180) completely describe all minimal division-free algorithms for computing these systems. We also prove, as an immediate consequence of our results, that the multiplicative complexity of the quaternion product over a real field is 8.     

Witt’s theorems for Galois Ring valued quadratic forms

We prove Witt’s cancelation and extension theorems for Galois Ring valued quadratic forms. The proof is based on the properties of the invariant I, previously defined by the authors, that classifies, together with the type of the corresponding bilinear form (alternating or not), nonsingular Galois Ring valued quadratic forms. Our results extend the Witt’s theorem for mod four valued quadratic forms. On the other hand, the known relation between the invariant I and the Arf invariant of an ordinary quadratic form (if the associated nonsingular bilinear form is alternating) is extended to the nonalternating case by explaining the invariant I in terms of Clifford algebras.     

Quantum Summation with an Application to Integration

We study summation of sequences and integration in the quantum model of computation. We develop quantum algorithms for computing the mean of sequences that satisfy a p-summability condition and for integration of functions from Lebesgue spaces L_p([0, 1]^d), and analyze their convergence rates. We also prove lower bounds showing that the proposed algorithms are, in many cases, optimal within the setting of quantum computing. This extends recent results of G. Brassard et al. (2000, “Quantum Amplitude Amplification and Estimation,” Technical Report, http://arXiv.org/abs/quant-ph/0005055) on computing the mean for bounded sequences and complements results of E. Novak (2001, J. Complexity17, 2–16) on integration of functions from Hölder classes. The analysis requires an appropriate model of quantum computation, capable of covering the typical features of numerical problems such as dealing with real numbers and real-valued functions and with vector and function spaces. We develop and study such a model, which can be viewed as a quantum setting for information-based complexity theory.     

Quadratic mappings of spheres

In this paper we obtain a basis-free method for determining the general form of quadratic maps over R between spheres. We show that all quadratic maps (over certain R-lattices) between spheres are Hopf maps, and that the classical Hopf fibrations, S^2m?1→S^m, for m=2, 4, 8, are the unique nontrivial maps over Z, up to action by the orthogonal group.     

A class of quadratically convergent algorithms for constrained function minimization

The problem of minimizing a functionf(x) subject to the constraint ?(x)=0 is considered. Here,f is a scalar,x is ann-vector, and ? is anm-vector, wherem <n. A general quadratically convergent algorithm is presented. The conjugate-gradient algorithm and the variable-metric algorithms for constrained function minimization can be obtained as particular cases of the general algorithm. It is shown that, for a quadratic function subject to a linear constraint, all the particular algorithms behave identically if the one-dimensional search for the stepsize is exact. Specifically, they all produce the same sequence of points and lead to the constrained minimal point in no more thann ?r descent steps, wherer is the number of linearly independent constraints. The algorithms are then modified so that they can also be employed for a nonquadratic function subject to a nonlinear constraint. Some particular algorithms are tested through several numerical examples.     

Computing upper and lower bounds in interval decision trees

This article presents algorithms for computing optima in decision trees with imprecise probabilities and utilities. In tree models involving uncertainty expressed as intervals and/or relations, it is necessary for the evaluation to compute the upper and lower bounds of the expected values. Already in its simplest form, computing a maximum of expectancies leads to quadratic programming (QP) problems. Unfortunately, standard optimization methods based on QP (and BLP – bilinear programming) are too slow for the evaluation of decision trees in computer tools with interactive response times. Needless to say, the problems with computational complexity are even more emphasized in multi-linear programming (MLP) problems arising from multi-level decision trees. Since standard techniques are not particularly useful for these purposes, other, non-standard algorithms must be used. The algorithms presented here enable user interaction in decision tools and are equally applicable to all multi-linear programming problems sharing the same structure as a decision tree.     

On bounded multilinear forms on a class of lp spaces

In this paper we generalize an old result of Littlewood and Hardy about bilinear forms defined in a class of sequence spaces. Historically, Littlewood [Quart. J. Math.1 (1930)] first proved a result on bilinear forms on bounded sequences and this result was then generalized by Hardy and Littlewood in a joint paper [Quart. J. Math.5(1934)] to bilinear forms on a class of l^p spaces. Later Davie and Kaijser proved Littlewood's results for multilinear forms. In this paper, Theorems A and B generalize the results to multilinear forms on l^p spaces. All the results are stated at the end of Section 1. Theorems A and B are proved, respectively, in Sections 2 and 3.     

Randomized first order algorithms with applications to ℓ 1-minimization

In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of the solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of ? ₁ minimization arising in sparsity-oriented signal processing. We demonstrate, both theoretically and by numerical examples, that when seeking for medium-accuracy solutions of large-scale ? ₁ minimization problems, our randomized algorithms outperform significantly (and progressively as the sizes of the problem grow) the state-of-the art deterministic methods.     

On the solution of NP-hard linear complementarity problems

In this paper two enumerative algorithms for the Linear Complementarity Problems (LCP) are discussed. These procedures exploit the equivalence of theLCP into a nonconvex quadratic and a bilinear programs. It is shown that these algorithms are efficient for processing NP-hardLCPs associated with reformulations of the Knapsack problem and should be recommended to solve difficultLCPs.     

Complexity of multiplication in commutative group algebras over fields of characteristic 0

Let rkA denote the bilinear complexity (also known as rank) of a finite-dimension associative algebra A. Algebras of minimal rank are widely studied from the point of view of bilinear complexity. These are the algebras A for which the Alder-Strassen inequality is satisfied as an equality, i.e., rkA = 2dimA ? t, where t is the number of maximum two-sided ideals in A. It is proved in this work that an arbitrary commutative group algebra over a field of characteristic 0 is an algebra of minimal rank. The structure and precise values of the bilinear complexity of commutative group algebras over a field of rational numbers are obtained.     

A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given.     

On the direct sum conjecture

We prove the direct sum conjecture for various sets of systems of bilinear forms. Our results depend on a priori knowledge of the complexity of at least one of the direct summands and its underlying algebraic structure. We also briefly survey some previous results concerning the complexity and structure of minimal algorithms for various direct sum systems.     

Ring structures and the discrete Fourier transform

Since the pioneering work of J. W. Cooley and J. W. Tukey Math. Comp.19 1965 297–301, a great deal of effort has been devoted to developing efficient algorithms for computing finite Fourier transform. Among the new methods suggested over the past several years, methods depending on ring-theoretic structures have received special attention. This approach, originally suggested by C. Rader (Proc. IEEE5, 6 1968, 1107–1108), was really developed by S. Winograd (“Arithmetic Complexity of Computations,” CBMS-NSF Regional Conference Series in Applied Mathematics 1980 into a powerful new algorithm. Winograd's real contribution was to realize that there are efficient algorithms to evaluate cyclic convolution. The purpose of this article is twofold: first, to make more explicit the interplay between ring-theoretic structures and the algorithms for the finite Fourier transform; second, to use this new insight to construct new algorithms for evaluating the finite Fourier transform on the groups $\text{Z}\text{(p}{}^{\mathrm{s}}\text{Z)}\text{⊕}\text{Z}\text{(p}{}^{\mathrm{s}}\text{Z)}\text{⊕ … ⊕}\text{Z}\text{(p}{}^{\mathrm{s}}\text{Z)}$.     

Worst-case complexity bounds for algorithms in the theory of integral quadratic forms

The problem of factoring an integer and many other number-theoretic problems can be formulated in terms of binary quadratic Diophantine equations. This class of equations is also significant in complexity theory, subclasses of it having provided most of the natural examples of problems apparently intermediate in difficulty between P and NP-complete problems, as well as NP-complete problems [2, 3, 22, 26]. The theory of integral quadratic forms developed by Gauss gives some of the deepest known insights into the structure of classes of binary quadratic Diophantine equations. This paper establishes explicit polynomial worst-case running time bounds for algorithms to solve certain of the problems in this theory. These include algorithms to do the following: (1) reduce a given integral binary quadratic form; (2) quasi-reduce a given integral ternary quadratic form; (3) produce a form composed of two given integral binary quadratic forms; (4) calculate genus characters of a given integral binary quadratic form, when a complete prime factorization of its determinant D is given as input; (5) produce a form that is the square root under composition of a given form (when it exists), when a complete factorization of D and a quadratic nonresidue for each prime dividing D is given as input.     

Optimal adaptive solution of initial-value problems with unknown singularities

The optimal solution of initial-value problems in ODEs is well studied for smooth right-hand side functions. Much less is known about the optimality of algorithms for singular problems. In this paper, we study the (worst case) solution of scalar problems with a right-hand side function having r   continuous bounded derivatives in R$\mathbf{R}$, except for an unknown singular point. We establish the minimal worst case error for such problems (which depends on r similarly as in the smooth case), and define optimal adaptive algorithms. The crucial point is locating an unknown singularity of the solution by properly adapting the grid. We also study lower bounds on the error of an algorithm for classes of singular problems. In the case of a single singularity with nonadaptive information, or in the case of two or more singularities, the error of any algorithm is shown to be independent of r.     

On interpolation of bilinear operators

In this paper we study interpolation of bilinear operators between products of Banach spaces generated by abstract methods of interpolation in the sense of Aronszajn and Gagliardo. A variant of bilinear interpolation theorem is proved for bilinear operators from corresponding weighted c₀ spaces into Banach spaces of non-trivial the periodic Fourier cotype. This result is then extended to the spaces generated by the well-known minimal and maximal methods of interpolation determined by quasi-concave functions. In the case when a maximal construction is generated by Hilbert spaces, we obtain a general variant of bilinear interpolation theorem. Combining this result with the abstract Grothendieck theorem of Pisier yields further results. The results are applied in deriving a bilinear interpolation theorem for Calderón-Lozanovsky, for Orlicz spaces and an embedding interpolation formula for (E,p)-summing operators.     

Applications of autoreproducing kernel grammian moduli to S (U,H)-valued stationary random functions

It is shown that the analytical characterizations of q-variate interpolable and minimal stationary processes obtained by H. Salehi (Ark. Mat., 7 (1967), 305–311; Ark. Mat., 8 (1968), 1–6; J. Math. Anal. Appl., 25 (1969), 653–662), and later by A. Weron (Studia Math., 49 (1974), 165–183), can be easily extended to Hilbert space valued stationary processes when using the two grammian moduli that respectively autoreproduce their correlation kernel and their spectral measure. Furthermore, for these processes, a Wold-Cramér concordance theorem is obtained that generalizes an earlier result established by H. Salehi and J. K. Scheidt (J. Multivar. Anal., 2 (1972), 307–331) and by A. Makagon and A. Weron (J. Multivar. Anal., 6 (1976), 123–137).     

Computational Complexity over thep-adic Numbers

A model of computation over thep-adic numbers, for odd primesp, is defined following the approach of Blum, Shub, and Smale. This model employs branching on the property of being a square inQ_pand unit height. The feasibility of systems of quadratic polynomials is shown to be NP-complete in this model. A polynomial time algorithm is given for feasibility of a single quadratic polynomial overQ_p.     

Guaranteed control in differential games with ellipsoidal payoff

A class of antagonistic linear differential games (DGs) in a fixed time interval with ellipsoidal payoff functional is considered. This class of DGs includes problems which assume both rigid constraints on the players' controls and requirements to minimize control expenses. Other known classes of differential games, such as linear DGs with a quadratic performance index and linear DGs with ellipsoidal terminal sets and admissible sets of controls for the players, considered in Kurzhanskii's ellipsoidal technique, are limiting cases of DGs of this class. The concept of a u-strategic function, which expresses the property of u-stability for ellipsoidal functions, is introduced. An effective algorithm is presented for computing a u-strategic function, based on Kurzhanskii's ellipsoidal technique. The main result of this paper is that a guaranteed positional strategy for player u is defined by a certain explicit formula in terms of a u-strategic function. The proof of this result is based on a viability theorem for differential equations.