Constrained multi-degree reduction of triangular Bézier surfaces using dual Bernstein polynomials

We propose a novel approach to the problem of multi-degree reduction of Bézier triangular patches with prescribed boundary control points. We observe that the solution can be given in terms of bivariate dual discrete Bernstein polynomials. The algorithm is very efficient thanks to using the recursive properties of these polynomials. The complexity of the method is O(n²m²), n and m being the degrees of the input and output Bézier surfaces, respectively. If the approximation—with appropriate boundary constraints—is performed for each patch of several smoothly joined triangular Bézier surfaces, the result is a composite surface of global C^r continuity with a prescribed order r. Some illustrative examples are given.     

A Komlós Theorem for abstract Banach lattices of measurable functions

Consider a Banach function space X(μ) of (classes of) locally integrable functions over a σ-finite measure space (Ω,Σ,μ) with the weak σ-Fatou property. Day and Lennard (2010) [9] proved that the theorem of Komlós on convergence of Cesàro sums in L¹[0,1] holds also in these spaces; i.e. for every bounded sequence n(fn) in X(μ), there exists a subsequence k(fnk) and a function f∈X(μ) such that for any further subsequence j(hj) of k(fnk), the series converges μ-a.e. to f. In this paper we generalize this result to a more general class of Banach spaces of classes of measurable functions — spaces L¹(ν) of integrable functions with respect to a vector measure ν on a δ-ring — and explore to which point the Fatou property and the Komlós property are equivalent. In particular we prove that this always holds for ideals of spaces L¹(ν) with the weak σ-Fatou property, and provide an example of a Banach lattice of measurable functions that is Fatou but do not satisfy the Komlós Theorem.     

Quadratic forms on completely symmetric spaces

Let V be an n-dimensional Euclidean vector space, and let V(^m) be the corresponding m-th completely symmetric space over V equipped with the induced inner product. The purpose of this paper is to prove the following conjecture of H.A. Robinson: if T is a linear operator on V(^m) and (Tz, z) = 0 for every decomposable element z of V(^m), then T is skew-symmetric.     

Pseudospectra, critical points and multiple eigenvalues of matrix polynomials

We develop a general framework for perturbation analysis of matrix polynomials. More specifically, we show that the normed linear space L_m(C^n×n) of n-by-n matrix polynomials of degree at most m provides a natural framework for perturbation analysis of matrix polynomials in L_m(C^n×n). We present a family of natural norms on the space L_m(C^n×n) and show that the norms on the spaces C^m+1 and C^n×n play a crucial role in the perturbation analysis of matrix polynomials. We define pseudospectra of matrix polynomials in the general framework of the normed space L_m(C^n×n) and show that the pseudospectra of matrix polynomials well known in the literature follow as special cases. We analyze various properties of pseudospectra in the unified framework of the normed space L_m(C^n×n). We analyze critical points of backward errors of approximate eigenvalues of matrix polynomials and show that each critical point is a multiple eigenvalue of an appropriately perturbed polynomial. We show that common boundary points of components of pseudospectra of matrix polynomials are critical points. As a consequence, we show that a solution of Wilkinson’s problem for matrix polynomials can be read off from the pseudospectra of matrix polynomials.     

Multi-degree reduction of tensor product Bézier surfaces with general boundary constraints

We propose an efficient approach to the problem of multi-degree reduction of rectangular Bézier patches, with prescribed boundary control points. We observe that the solution can be given in terms of constrained bivariate dual Bernstein polynomials. The complexity of the method is O(mn₁n₂) with m ? min(m₁, m₂), where (n₁, n₂) and (m₁, m₂) is the degree of the input and output Bézier surface, respectively. If the approximation—with appropriate boundary constraints—is performed for each patch of several smoothly joined rectangular Bézier surfaces, the result is a composite surface of global C^r continuity with a prescribed r ? 0. In the detailed discussion, we restrict ourselves to r ∈ {0, 1}, which is the most important case in practical application. Some illustrative examples are given.     

Classifying Hilbert bundles

A Hilbert bundle (p, B, X) is a type of fibre space p:B → X such that each fibre p^?1(x) is a Hilbert space. However, p^?1(x) may vary in dimension as x varies in X. We generalize the classical homotopy classification theory of vector bundles to a “homotopy” classification of certain Hilbert bundles. An (m, n)-bundle over the pair (X, A) is a Hilbert bundle (p, B, X) such that the dimension of p^?1(x) is m for x in A and n otherwise. The main result here is that if A is a compact set lying in the “edge” of the metric space X (e.g. if X is a topological manifold and A is a compact subset of the boundary of X), then the problem of classifying (m, n)-bundles over (X, A) reduces to a problem in the classical theory of vector bundles. In particular, we show there is a one-to-one correspondence between the members of the orbit set, [A, G_m($\text{C}$ⁿ)]/[X, U(n)] ¦ A, and the isomorphism classes of (m, n)-bundles over (X, A) which are trivial over X, A.     

Vector measure Maurey–Rosenthal-type factorizations and -sums of -spaces

Consider a vector measure of bounded variation m with values in a Banach space and an operator T:XL¹(m), where L¹(m) is the space of integrable functions with respect to m. We characterize when T can be factorized through the space L²(m) by means of a multiplication operator given by a function of L²(|m|), where |m| is the variation of m, extending in this way the Maurey–Rosenthal Theorem. We use this result to obtain information about the structure of the space L¹(m) when m is a sequential vector measure. In this case the space L¹(m) is an ℓ-sum of L¹-spaces.     

On isometric immersions with flat normal connection of the hyperbolic space L n into Euclidean space E n+m

We prove that the hyperbolic space L ⁿ cannot be immersed in an Euclidean space E ^n+m with a flat normal connection provided the module of the mean curvature vector is bounded.     

Branching laws for minimal holomorphic representations

In this paper we study the branching law for the restriction from SU(n,m) to SO(n,m) of the minimal representation in the analytic continuation of the scalar holomorphic discrete series. We identify the group decomposition with the spectral decomposition of the action of the Casimir operator on the subspace of S(O(n)×O(m))-invariants. The Plancherel measure of the decomposition defines an L²-space of functions, for which certain continuous dual Hahn polynomials furnish an orthonormal basis. It turns out that the measure has point masses precisely when n−m>2. Under these conditions we construct an irreducible representation of SO(n,m), identify it with a parabolically induced representation, and construct a unitary embedding into the representation space for the minimal representation of SU(n,m).     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

Multiple point evaluation on combined tensor product supports

We consider the multiple point evaluation problem for an n-dimensional space of functions [???1,1[ ^d ?? spanned by d-variate basis functions that are the restrictions of simple (say linear) functions to tensor product domains. For arbitrary evaluation points this task is faced in the context of (semi-)Lagrangian schemes using adaptive sparse tensor approximation spaces for boundary value problems in moderately high dimensions. We devise a fast algorithm for performing m?≥?n point evaluations of a function in this space with computational cost O(mlog ^d n). We resort to nested segment tree data structures built in a preprocessing stage with an asymptotic effort of O(nlog ^d???1 n).     

Some inverse results for Hill's equation

We consider Hill's equation y″+(λ−q)y=0 where q∈L¹[0,π]. We show that if l_n—the length of the n-th instability interval—is of order O(n^−(k+2)) then the real Fourier coefficients a_n^k,b_n^k of q^(k)—k-th derivative of q—are of order O(n⁻²), which implies that q^(k) is absolutely continuous almost everywhere for k=0,1,2,….     

Grassmannians of 2-Sided Vector Spaces

Let k ? K be an extension of fields, and let A ? M _n (K) be a k-algebra. We study parameter spaces of m-dimensional subspaces of K ⁿ which are invariant under A. The space  _A (m, n), whose R-rational points are A-invariant, free rank m summands of R ⁿ , is well known. We construct a distinct parameter space,  _A (m, n), which is a fiber product of a Grassmannian and the projectivization of a vector space. We then study the intersection  _A (m, n) ∩  _A (m, n), which we denote by  _A (m, n). Under suitable hypotheses on A, we construct affine open subschemes of  _A (m, n) and  _A (m, n) which cover their K-rational points. We conclude by using  _A (m, n),  _A (m, n), and  _A (m, n) to construct parameter spaces of 2-sided subspaces of 2-sided vector spaces.     

Multiplication operators on vector measure Orlicz spaces

Let m be a countably additive vector measure with values in a real Banach space X, and let L¹(m) and L_w(m) be the spaces of functions which are, correspondingly, integrable and weakly integrable with respect to m. Given a Young's function Φ, we consider the vector measure Orlicz spaces L^Φ(m) and L^Φ_w(m) and establish that the Banach space of multiplication operators going from W = L^Φ(m) into Y = L¹ (m) is M = L^Ψ_w (m) with an equivalent norm; here Ψ is the conjugated Young's function for Φ. We also prove that when W = L^Φ_w(m), Y = L¹(m) we have M = L^Ψ_w (m), and when W = L^Φ_w(m), Y = L¹(m) we have M = L^Ψ (m).     

Convexity of trace functionals and Schrödinger operators

Let H be a semi-bounded self-adjoint operator on a separable Hilbert space. For a certain class of positive, continuous, decreasing, and convex functions F we show the convexity of trace functionals of the form tr(F(H+U−ε(U)))−ε(U), where U is a bounded, self-adjoint operator and ε(U) is a normalizing real function—the Fermi level—which may be identical zero. If additionally F is continuously differentiable, then the corresponding trace functional is Fréchet differentiable and there is an expression of its gradient in terms of the derivative of F. The proof of the differentiability of the trace functional is based upon Birman and Solomyak's theory of double Stieltjes operator integrals. If, in particular, H is a Schrödinger-type operator and U a real-valued function, then the gradient of the trace functional is the quantum mechanical expression of the particle density with respect to an equilibrium distribution function f=−F^′. Thus, the monotonicity of the particle density in its dependence on the potential U of Schrödinger's operator—which has been understood since the late 1980s—follows as a special case.     

On lines, joints, and incidences in three dimensions

We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz (2010) [9], to obtain several sharp bounds on the number of incidences between lines and points in three dimensions. Specifically, we show: (i) The maximum possible number of incidences between n lines in R³ and m of their joints (points incident to at least three non-coplanar lines) is Θ(m1/3n) for m?n, and Θ(m2/3n2/3+m+n) for m?n. (ii) In particular, the number of such incidences cannot exceed O(n3/2). (iii) The bound in (i) also holds for incidences between n lines and m arbitrary points (not necessarily joints), provided that no plane contains more than O(n) points and each point is incident to at least three lines. As a preliminary step, we give a simpler proof of (an extension of) the bound O(n3/2), established by Guth and Katz, on the number of joints in a set of n lines in R³. We also present some further extensions of these bounds, and give a trivial proof of Bourgain's conjecture on incidences between points and lines in 3-space, which is an immediate consequence of our incidence bounds, and which constitutes a much simpler alternative to the proof of Guth and Katz (2010) [9].     

An exact algorithm for MAX-CUT in sparse graphs

We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O^*(2^(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O^*(2^mn/(m+n)). Both algorithms use polynomial space.     

An Efficient Algorithm for the Complex Roots Problem

Given a univariate polynomialf(z) of degreenwith complex coefficients, whose norms are less than 2^min magnitude, the root problem is to find all the roots off(z) up to specified precision 2^−μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexityO(nlog⁵nlogB), whereb= χ + μ, and χ = max{n,m}. This improves on the previous best known algorithm of Pan for the problem, which has complexityO(n²log²nlog(m+ μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation off, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = ⌈n(B+ logn+ 3)⌉ bits of the binary representations of the real and imaginary parts of each of the coefficients off. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where[formula]and[formula]Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor ofM(φ) (whereM(ψ) =O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and “centered” points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel timeO(log⁶nlogB) usingnprocessors.     

Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log² m log² n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m²+n)log m) andO((m²+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]¹⁺ log² n) time, for any >0.     

Ordered representations of spaces of integrable functions

Let X be a Banach space, (Ω,Σ) a measurable space and let m : Σ → X be a (countably additive) vector measure. Consider the corresponding space of integrable functions L¹(m). In this paper we analyze the set of (countably additive) vector measures n satisfying that L¹(n) = L¹(m). In order to do this we define a (quasi) order relation on this set to obtain under adequate requirements the simplest representation of the space L¹(m) associated to downward directed subsets of the set of all the representations. This research has been partially supported by La Junta de Andalucía. The support of D.G.I. under project MTM2006–11690–C02 (M.E.C. Spain) and FEDER is gratefully acknowledged.