Solving the linear least squares problem with very high relative accuracy

A version of binary cascades iterative refinement (LSBCIR) for solving linear least squares problem min _x ‖b-Ax‖₂,A(m*n),m>n=rank(A), to a prescribed accuracy ε>0 is proposed and investigated. The time cost of the process in the sequential computation is of order $$mn^2 M(t_0 ) + mnM\left( {\left\lceil {\log _2 /\varepsilon } \right\rceil } \right)$$ , wheret ₀ is a basic mantissa length andM(t)=Kt ² is the time cost of two numbers multiplication infl(t).     

A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively, be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest common subsequence of two given strings X and Y in O(kl+min{p₁,p₂}) time, where p₁ and p₂ denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. It improves the previously known time bound O(min{nl,km}) and outperforms the time bounds O(kllogkl) or O((k+l+q)log(k+l+q)) for some cases, where q denotes the number of matched blocks.     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

An error bound for approximate solutions of two-point boundary value problems

A new error bound for any approximate solutionu of the two-point boundary value problemAy:=?(py′)′+qy=f,y(0)=0, y(1)=0, is proposed. This error bound depends on the deviationAu?fjust like the one which is proportional to ‖Au?f‖₂, but in the case of Ritz-Galerkin approximations by cubic splines it behaves asymptotically likeh ³, whereh is the knot distance, i.e., it is by one order of magnitude better. An important advantage of this error bound is that it can be used even in the case of generalized solutions and of piecewise linear approximations. An error bound for the approximation of the derivative results also from these considerations. This error bound behaves in the above case asymptotically also likeh ³, i.e. it has the same asymptotic behaviour as the actual approximation error of the derivative.     

Spurious solutions for discrete superlinear boundary value problems

We consider finite dimensional nonlinear eigenvalue problems of the typeAu=λFu whereA is a matrix and(Fu) _i =f(u _i ),i=1, ...,m. These may be thought of as discretizations of a corresponding boundary value problem. We show that positive, spurious solution branches of the discrete equations (which have been observed in some cases in [1, 7]) typically arise iff increases sufficiently strong and ifA ^?1 has at least two positive columns of a certain type. We treat in more detail the casesf(u)=e ^u andf(u)=u ^α where also discrete bifurcation diagrams are given.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^1.5k ?^?1.5k (α(n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, α is the inverse Ackermann function, and ? ≤ 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ?) times the weight of a minimum weight complete matching.     

Ritz-Galerkin Verfahren für normale Operatoren im Hilbertraum

Interpreting the Ritz method as a procedure to compute elements of best approximation for the norm ‖z‖ _R ² =(Az, z), similar methods are obtained in substituting ‖ ‖ _g with ‖z‖ _g =‖g(A)z‖ for a suitable functiong in place of ‖ ‖ _R . Such methods are applicable to large classes of linear operators. Taking bounded or unbounded, normal operators forA and polynomials in the variablesw and \(\bar w\) forg it is demonstrated how to get some estimations of the error.     

Some new sequence spaces derived by the domain of the triple band matrix

Let λ denote any of the classical spaces ?_∞,c,c₀, and ?_p of bounded, convergent, null, and absolutely p-summable sequences, respectively, and let λ(B) also be the domain of the triple band matrix B(r,s,t) in the sequence space λ, where 1<p<∞. The present paper is devoted to studying the sequence space λ(B). Furthermore, the β- and γ-duals of the space λ(B) are determined, the Schauder bases for the spaces c(B), c₀(B), and ?_p(B) are given, and some topological properties of the spaces c₀(B), ?₁(B), and ?_p(B) are examined. Finally, the classes (λ₁(B):λ₂) and (λ₁(B):λ₂(B)) of infinite matrices are characterized, where λ₁∈{?_∞,c,c₀,?_p,?₁} and λ₂∈{?_∞,c,c₀,?₁}.     

Routing equal-size messages on a slotted ring

We deal with the problem of routing messages on a slotted ring network in this paper. We study the computational complexity and algorithms for this routing by means of the results known in the literature for the multi-slot just-in-time scheduling problem. We consider two criteria for the routing problem: makespan, or minimum routing time, and diagonal makespan. A?diagonal is simply a schedule of ring links i=0,??,q?1 in q consecutive time slots, respectively. The number of diagonals between the earliest and the latest diagonals with non-empty packets is referred to as the diagonal makespan. For the former, we show that the optimal routing of messages of size k, is NP-hard in the strong sense, while an optimal routing when k=q can be computed in O(n ²log² n) time. We also give an O(nlogn)-time constant factor approximation algorithm for unit size messages. For the latter, we prove that the optimal routing of messages of size k, where k divides the size of the ring q, is NP-hard in the strong sense even for any fixed k??1, while an optimal routing when k=q can be computed in O(nlogn) time. We also give an O(nlogn)-time approximation algorithm with an absolute error 2q?k.     

Computing largest empty circles with location constraints

LetQ = {q₁, q₂,..., q_n} be a set ofn points on the plane. The largest empty circle (LEG) problem consists in finding the largest circleC with center in the convex hull ofQ such that no pointq _i εQ lies in the interior ofC. Shamos recently outlined anO(n logn) algorithm for solving this problem.⁽⁹⁾ In this paper it is shown that this algorithm does not always work correctly. A different approach is proposed here and shown to also result in anO(n logn) algorithm. The new approach has the advantage that it can also solve more general problems. In particular, it is shown that if the center ofC is constrained to lie in an arbitrary convexn-gon, an0(n logn) algorithm can still be obtained. Finally, an0(n logn +k logn) algorithm is given for solving this problem when the center ofC is constrained to lie in an arbitrary simplen-gonP. wherek denotes the number of intersections occurring between edges ofP and edges of the Voronoi diagram ofQ andk ?O(n ²).     

The super-connected property of recursive circulant graphs

In a graph G, a k-container C_k(u,v) is a set of k disjoint paths joining u and v. A k-container C_k(u,v) is k∗-container if every vertex of G is passed by some path in C_k(u,v). A graph G is k∗-connected if there exists a k∗-container between any two vertices. An m-regular graph G is super-connected if G is k∗-connected for any k with 1?k?m. In this paper, we prove that the recursive circulant graphs G(2^m,4), proposed by Park and Chwa [Theoret. Comput. Sci. 244 (2000) 35-62], are super-connected if and only if m≠2.     

Diameter variability of cycles and tori

The diameter of a graph is an important factor for communication as it determines the maximum communication delay between any pair of processors in a network. Graham and Harary [N. Graham, F. Harary, Changing and unchanging the diameter of a hypercube, Discrete Applied Mathematics 37/38 (1992) 265-274] studied how the diameter of hypercubes can be affected by increasing and decreasing edges. They concerned whether the diameter is changed or remains unchanged when the edges are increased or decreased. In this paper, we modify three measures proposed in Graham and Harary (1992) to include the extent of the change of the diameter. Let D^-k(G) is the least number of edges whose addition to G decreases the diameter by (at least) k, D⁺⁰(G) is the maximum number of edges whose deletion from G does not change the diameter, and D^+k(G) is the least number of edges whose deletion from G increases the diameter by (at least) k. In this paper, we find the values of D^-k(C_m), D^-1(T_m,n), D^-2(T_m,n), D⁺¹(T_m,n), and a lower bound for D⁺⁰(T_m,n) where C_m be a cycle with m vertices, T_m,n be a torus of size m by n.     

Asymptotic behavior of nonoscillatory solutions of neutral difference equations

The authors consider the m^th-order neutral difference equation D_m(y(n) + p(n)y(n − k) + q(n)f(y(σ(n))) = e(n), where m ≥ 1, {p(n)}, {q(n)}, {e(n)}, and {a₁(n)}, {a₂(n)}, …, {a_m−1(n)} are real sequences, a_i(n) > 0 for i = 1,2,…, m−1, a_m(n) ≡ 1, D₀z(n) = y(n)+p(n)y(n − k), D_iz(n) = a_i(n)ΔD_i−1z(n) for i = 1,2, …, m, k is a positive integer, {σ(n)} → ∞ is a sequence of positive integers, and R → R is continuous with u f(u) > 0 for u ≠ 0. In the case where {q(n)} is allowed to oscillate, they obtain sufficient conditions for all bounded nonoscillatory solutions to converge to zero, and if {q(n)} is a nonnegative sequence, they establish sufficient conditions for all nonoscillatory solutions to converge to zero. Examples illustrating the results are included throughout the paper.     

Positivity properties in pencils of matrices†

If A and B are positive definite self-adjoint matrices, then all the matrices P_i, occurring in the expansion of an exterior power Λ^k(A+ λB) = P ₀ + P ₁λ + … + P _kλ^k are positive definite.     

The perturbation of the Drazin inverse

In this paper, we present the explicit expressions of the perturbation of the Drazin inverse under different conditions. Also, we give the upper bounds of ‖(A+E)^D?A ^D‖ _P /‖A ^D‖ _P for these cases.     

Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ?^d so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n <m <n ^d ), then we show that it is possible to answer any query inO(n ^1+?/m ^1/d ) query time afterO(m ^1+?) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n ^d+?) storage for any fixed ? > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.     

QFT template generation for time-delay plants based on zero-inclusion test

Plant template generation is the key step in applying quantitative feedback theory (QFT) to design robust control for uncertain systems. In this paper we propose a technique for generating plant templates for a class of linear systems with an uncertain time delay and affine parameter perturbations in coefficients. The main contribution lies in presenting a necessary and sufficient condition for the zero inclusion of the value set f(T,Q)={f(τ,q): τT[τ⁻,τ⁺], qQ∏_k=0^m−1[q_k⁻,q_k⁺]}, where f(τ,q)=g(q)+h(q)e^−jτω*, g(q) and h(q) are both complex-valued affine functions of the m-dimensional real vector q, and ω^* is a fixed frequency. Based on this condition, an efficient algorithm which involves, in the worst case, evaluation of m algebraic inequalities and solution of m2^m−1 one-variable quadratic equations, is developed for testing the zero inclusion of the value set f(T,Q). This zero-inclusion test algorithm allows one to utilize a pivoting procedure to generate the outer boundary of a plant template with a prescribed accuracy or resolution. The proposed template generation technique has a linear computational complexity in resolution and is, therefore, more efficient than the parameter gridding and interval methods. A numerical example illustrating the proposed technique and its computational superiority over the interval method is included.     

On depth in EDTOL languages

Languages of the form L₁={aⁿ:n?1}, L₂={(abⁿ)^m: n,m?1}, L₃={(a(bcⁿ) ^m)^k: n,m,k?1}, etc. differ in what may be called ‘depth’. It turns out that this depth is closely related to the structure of finite state automata associated with EDTOL systems generating these languages. For a given system the corresponding automaton is defined, and the relevant characteristics of its structure are examined.     

Stronger Lempel-Ziv Based Compressed Text Indexing

Given a text T[1..u] over an alphabet of size σ, the full-text search problem consists in finding the occ occurrences of a given pattern P[1..m] in T. In indexed text searching we build an index on T to improve the search time, yet increasing the space requirement. The current trend in indexed text searching is that of compressed full-text self-indices, which replace the text with a more space-efficient representation of it, at the same time providing indexed access to the text. Thus, we can provide efficient access within compressed space. The Lempel-Ziv index (LZ-index) of Navarro is a compressed full-text self-index able to represent T using 4uH _k (T)+o(ulog?σ) bits of space, where H _k (T) denotes the k-th order empirical entropy of T, for any k=o(log? _σ u). This space is about four times the compressed text size. The index can locate all the occ occurrences of a pattern P in T in O(m ³log?σ+(m+occ)log?u) worst-case time. Although this index has proven very competitive in practice, the O(m ³log?σ) term can be excessive for long patterns. Also, the factor 4 in its space complexity makes it larger than other state-of-the-art alternatives. In this paper we present stronger Lempel-Ziv based indices (LZ-indices), improving the overall performance of the original LZ-index. We achieve indices requiring (2+ε)uH _k (T)+o(ulog?σ) bits of space, for any constant ε>0, which makes them the smallest existing LZ-indices. We simultaneously improve the search time to O(m ²+(m+occ)log?u), which makes our indices very competitive with state-of-the-art alternatives. Our indices support displaying any text substring of length ? in optimal O(?/log? _σ u) time. In addition, we show how the space can be squeezed to (1+ε)uH _k (T)+o(ulog?σ) to obtain a structure with O(m ²) average search time for m≥2log? _σ u. Alternatively, the search time of LZ-indices can be improved to O((m+occ)log?u) with (3+ε)uH _k (T)+o(ulog?σ) bits of space, which is much less than the space needed by other Lempel-Ziv-based indices achieving the same search time. Overall our indices stand out as a very attractive alternative for space-efficient indexed text searching.