Numerical solution to a linear equation with tensor product structure

We consider the numerical solution of a c‐stable linear equation in the tensor product space , arising from a discretized elliptic partial differential equation in . Utilizing the stability, we produce an equivalent d‐stable generalized Stein‐like equation, which can be solved iteratively. For large‐scale problems defined by sparse and structured matrices, the methods can be modified for further efficiency, producing algorithms of computational complexity, under appropriate assumptions (with n_s being the flop count for solving a linear system associated with ). Illustrative numerical examples will be presented.     

Directional ‐matrix compression for high‐frequency problems

Standard numerical algorithms, such as the fast multipole method or ‐matrix schemes, rely on low‐rank approximations of the underlying kernel function. For high‐frequency problems, the ranks grow rapidly as the mesh is refined, and standard techniques are no longer attractive. Directional compression techniques solve this problem by using decompositions based on plane waves. Taking advantage of hierarchical relations between these waves' directions, an efficient approximation is obtained. This paper is dedicated to directional ‐matrices that employ local low‐rank approximations to handle directional representations efficiently. The key result is an algorithm that takes an arbitrary matrix and finds a quasi‐optimal approximation of this matrix as a directional ‐matrix using a prescribed block tree. The algorithm can reach any given accuracy, and the approximation requires only units of storage, where n is the matrix dimension, κ is the wave number, and k is the local rank. In particular, we have a complexity of if κ is constant and for high‐frequency problems characterized by κ²～n. Because the algorithm can be applied to arbitrary matrices, it can serve as the foundation of fast techniques for constructing preconditioners.     

A constructive arbitrary‐degree Kronecker product decomposition of tensors

We generalize the matrix Kronecker product to tensors and propose the tensor Kronecker product singular value decomposition that decomposes a real k‐way tensor into a linear combination of tensor Kronecker products with an arbitrary number of d factors. We show how to construct , where each factor is also a k‐way tensor, thus including matrices (k=2) as a special case. This problem is readily solved by reshaping and permuting into a d‐way tensor, followed by a orthogonal polyadic decomposition. Moreover, we introduce the new notion of general symmetric tensors (encompassing symmetric, persymmetric, centrosymmetric, Toeplitz and Hankel tensors, etc.) and prove that when is structured then its factors will also inherit this structure.     

Singular‐value (and eigenvalue) distribution and Krylov preconditioning of sequences of sampling matrices approximating integral operators

Let k( ? , ? ) be a continuous kernel defined on Ω × Ω, Ω compact subset of , , and let us consider the integral operator from into ( set of continuous functions on Ω) defined as the map is a compact operator and therefore its spectrum forms a bounded sequence having zero as unique accumulation point. Here, we first consider in detail the approximation of by using rectangle formula in the case where Ω = [0,1], and the step is h = 1 ∕ n. The related linear application can be represented as a matrix A_n of size n. In accordance with the compact character of the continuous operator, we prove that {A_n} ～ _σ0 and {A_n} ～ _λ0, that is, the considered sequence has singular values and eigenvalues clustered at zero. Moreover, the cluster is strong in perfect analogy with the compactness of . Several generalizations are sketched, with special attention to the general case of pure sampling sequences, and few examples and numerical experiments are critically discussed, including the use of GMRES and preconditioned GMRES for large linear systems coming from the numerical approximation of integral equations of the form (1) with and datum g(x). Copyright © 2014 John Wiley & Sons, Ltd.     

Local reconstruction of low‐rank matrices and subspaces

We study the problem of reconstructing a low‐rank matrix, where the input is an n × m matrix M over a field and the goal is to reconstruct a (near‐optimal) matrix that is low‐rank and close to M under some distance function Δ. Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010). Our main result is a local reconstruction algorithm for the case where Δ is the normalized Hamming distance (between matrices). Given M that is ‐close to a matrix of rank (together with d and ), this algorithm computes with high probability a rank‐d matrix that is ‐close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry by reading only the data structure and 2d additional entries of M. We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When Δ is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when Δ is the truncated Euclidean distance and , we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: http://eccc.hpi-web.de/report/2015/128/ © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607–630, 2017     

The max‐length‐vector line of best fit to a set of vector subspaces and an optimization problem over a set of hyperellipsoids

Let be a collection of subspaces of a finite‐dimensional real vector space V. Let L denote a one‐dimensional subspace of V, and let θ(L,V_i) denote the principal angle between L and V_i. Motivated by a problem in data analysis, we seek an L that maximizes the function . Conceptually, this is the line through the origin that best represents with respect to the criterion F(L). A reformulation shows that L is spanned by a vector , which maximizes the function subject to the constraints v_i∈V_i and ||v_i||=1. In this setting, v is seen to be the longest vector that can be decomposed into unit vectors lying on prescribed hyperspheres. A closely related problem is to find the longest vector that can be decomposed into vectors lying on prescribed hyperellipsoids. Using Lagrange multipliers, the critical points of either problem can be cast as solutions of a multivariate eigenvalue problem. We employ homotopy continuation and numerical algebraic geometry to solve this problem and obtain the extremal decompositions. Copyright © 2015 John Wiley & Sons, Ltd.     

Constructions of Strictly m‐Cyclic and Semi‐Cyclic

An is a triple , where X is a set of points, is a partition of X into m disjoint sets of size n and is a set of 4‐element transverses of , such that each 3‐element transverse of is contained in exactly one of them. If the full automorphism group of an admits an automorphism α consisting of n cycles of length m (resp. m cycles of length n), then this is called m‐cyclic (resp. semi‐cyclic). Further, if all block‐orbits of an m‐cyclic (resp. semi‐cyclic) are full, then it is called strictly cyclic. In this paper, we construct some infinite classes of strictly m‐cyclic and semi‐cyclic , and use them to give new infinite classes of perfect two‐dimensional optical orthogonal codes with maximum collision parameter and AM‐OPPTS/AM‐OPPW property.     

The Game Saturation Number of a Graph

Given a family and a host graph H, a graph is ‐saturated relative to H if no subgraph of G lies in but adding any edge from to G creates such a subgraph. In the ‐saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in , until G becomes ‐saturated relative to H. They aim to maximize or minimize the length of the game, respectively; denotes the length under optimal play (when Max starts). Let denote the family of odd cycles and the family of n‐vertex trees, and write F for when . Our results include , for , for , and for . We also determine ; with , it is n when n is even, m when n is odd and m is even, and when is odd. Finally, we prove the lower bound . The results are very similar when Min plays first, except for the P₄‐saturation game on .     

Chordal 2‐Connected Graphs and Spanning Trees

We present a transformation on a chordal 2‐connected simple graph that decreases the number of spanning trees. Based on this transformation, we show that for positive integers n, m with , the threshold graph having n vertices and m edges that consists of an ‐clique and vertices of degree 2 is the only graph with the fewest spanning trees among all 2‐connected chordal graphs on n vertices and m edges.     

Large Cross‐Free Sets in Steiner Triple Systems

A cross‐free set of size m in a Steiner triple system is three pairwise disjoint m‐element subsets such that no intersects all the three ‐s. We conjecture that for every admissible n there is an STS(n) with a cross‐free set of size which if true, is best possible. We prove this conjecture for the case , constructing an STS containing a cross‐free set of size 6k. We note that some of the 3‐bichromatic STSs, constructed by Colbourn, Dinitz, and Rosa, have cross‐free sets of size close to 6k (but cannot have size exactly 6k). The constructed STS shows that equality is possible for in the following result: in every 3‐coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic connected component of size at least (we conjecture that equality holds for every admissible n). The analog problem can be asked for r‐colorings as well, if and is a prime power, we show that the answer is the same as in case of complete graphs: in every r‐coloring of the blocks of any STS(n), there is a monochromatic connected component with at least points, and this is sharp for infinitely many n.     

Rainbow matchings and Hamilton cycles in random graphs

Let be drawn uniformly from all m‐edge, k‐uniform, k‐partite hypergraphs where each part of the partition is a disjoint copy of . We let be an edge colored version, where we color each edge randomly from one of colors. We show that if and where K is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if n is even and where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in . Here denotes a random edge coloring of with n colors. When n is odd, our proof requires for there to be a rainbow Hamilton cycle. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 503–523, 2016     

On the Hamilton–Waterloo Problem with Odd Orders

Given nonnegative integers , the Hamilton–Waterloo problem asks for a factorization of the complete graph into α ‐factors and β ‐factors. Without loss of generality, we may assume that . Clearly, v odd, , , and are necessary conditions. To date results have only been found for specific values of m and n. In this paper, we show that for any integers , these necessary conditions are sufficient when v is a multiple of and , except possibly when or 3. For the case where we show sufficiency when with some possible exceptions. We also show that when are odd integers, the lexicographic product of with the empty graph of order n has a factorization into α ‐factors and β ‐factors for every , , with some possible exceptions.     

Hierarchical Construction of Bounded Solutions in Critical Regularity Spaces

We construct uniformly bounded solutions for the equations div U = f and U = f in the critical cases and , respectively. Criticality in this context manifests itself by the lack of a linear solution operator mapping . Thus, the intriguing aspect here is that although the problems are linear, construction of their solutions is not. Our constructions are special cases of a general framework for solving linear equations of the form , where is a linear operator densely defined in Banach space with a closed range in a (proper subspace) of Lebesgue space , and with an injective dual . The solutions are realized in terms of a multiscale hierarchical representation, , interesting for its own sake. Here, u _j's are constructed recursively as minimizers of where the residuals are resolved in terms of a dyadic sequence of scales with large enough . The nonlinear aspect of this construction is a counterpart of the fact that one cannot linearly solve in critical regularity spaces.© 2016 Wiley Periodicals, Inc.     

Volume estimates for sections of certain convex bodies

This paper deals with volume estimates for hyperplane sections of the simplex and for m‐codimensional sections of powers of m‐dimensional Euclidean balls. In the first part we consider sections through the centroid of the n‐dimensional regular simplex. We state a volume formula and give a lower bound for the volume of sections through the centroid. In the second part we study the extremal volumes of m‐codimensional sections “perpendicular” to of unit balls in the space for all . We give volume formulas and use them to show that the normal vector (1, 0, …, 0) yields the minimal volume. Furthermore we give an upper bound for the ‐dimensional volumes for natural numbers . This bound is asymptotically attained for the normal vector as .     

Saturation Numbers in Tripartite Graphs

Given graphs H and F, a subgraph is an F‐saturated subgraph of H if , but for all . The saturation number of F in H, denoted , is the minimum number of edges in an F‐saturated subgraph of H. In this article, we study saturation numbers of tripartite graphs in tripartite graphs. For and n₁, n₂, and n₃ sufficiently large, we determine and exactly and within an additive constant. We also include general constructions of ‐saturated subgraphs of with few edges for .     

Cycle‐Saturated Graphs with Minimum Number of Edges

A graph G is called H‐saturated if it does not contain any copy of H, but for any edge e in the complement of G, the graph contains some H. The minimum size of an n‐vertex H‐saturated graph is denoted by . We prove holds for all , where is a cycle with length k. A graph G is H‐semisaturated if contains more copies of H than G does for . Let be the minimum size of an n‐vertex H‐semisaturated graph. We have We conjecture that our constructions are optimal for . © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 203–215, 2013     

Note on a problem of M. Talagrand

Answering a question of M. Talagrand, we show that there is a fixed L with the following property. For positive integers and , if is the set of subgraphs of K_n containing at least copies of K_k, then there is a set of subgraphs of K_n such that (i) each member of contains a member of and (ii) (where means number of edges). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 663–668, 2015     

Existence of positive solutions to a coupled system of fractional differential equations

We consider the following system of fractional differential equations where is the Riemann‐Liouville fractional derivative of order α,f,g : [0,1] × [0, ∞ ) × [0, ∞ ) → [0, ∞ ). Sufficient conditions are provided for the existence of positive solutions to the considered problem. Copyright © 2014 John Wiley & Sons, Ltd.     

Circular Chromatic Indices of Regular Graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are adjacent. It is known that for any , there is a 3‐regular simple graph G with . This article proves the following results: Assume is an odd integer. For any , there is an n‐regular simple graph G with . For any , there is an n‐regular multigraph G with .     

A Hypercube Variant with Small Diameter

This article introduces a new variant of hypercubes . The n‐dimensional twisted hypercube is obtained from two copies of the ‐dimensional twisted hypercube by adding a perfect matching between the vertices of these two copies of . We prove that the n‐dimensional twisted hypercube has diameter . This improves on the previous known variants of hypercube of dimension n and is optimal up to an error of order . Another type of hypercube variant that has similar structure and properties as is also discussed in the last section.