Based on the column pivoted QR decomposition, we propose some randomized algorithms including pass-efficient ones for the generalized CUR decompositions of matrix pair and matrix triplet. Detailed error analyses of th...
详细信息
Based on the column pivoted QR decomposition, we propose some randomized algorithms including pass-efficient ones for the generalized CUR decompositions of matrix pair and matrix triplet. Detailed error analyses of these algorithms are provided. Numerical experiments are given to test the proposed randomized algorithms.
Iterative sketching and sketch-and-precondition are randomized algorithms used for solving overdetermined linear least-squares problems. When implemented in exact arithmetic, these algorithms produce high-accuracy sol...
详细信息
Iterative sketching and sketch-and-precondition are randomized algorithms used for solving overdetermined linear least-squares problems. When implemented in exact arithmetic, these algorithms produce high-accuracy solutions to least-squares problems faster than standard direct methods based on QR factorization. Recently, Meier et al. demonstrated numerical instabilities in a version of sketch-and-precondition in floating point arithmetic. The work of Meier et al. raises the question, is there a randomized least-squares solver that is both fast and stable? This paper resolves this question in the affirmative by proving that iterative sketching, appropriately implemented, is forward stable. Numerical experiments confirm the theoretical findings, demonstrating that iterative sketching is stable and faster than QR-based solvers for large problem instances.
We consider the online metric matching problem in which we are given a metric space, k of whose points are designated as servers. Over time, up to k requests arrive at an arbitrary subset of points in the metric space...
详细信息
We consider the online metric matching problem in which we are given a metric space, k of whose points are designated as servers. Over time, up to k requests arrive at an arbitrary subset of points in the metric space, and each request must be matched to a server immediately upon arrival, subject to the constraint that at most one request is matched to any particular server. Matching decisions are irrevocable and the goal is to minimize the sum of distances between the requests and their matched servers. We give an O(log(2) k)-competitive randomized algorithm for the online metric matching problem. This improves upon the best known guarantee of O(log(3) k) on the competitive factor due to Meyerson, Nanavati and Poplawski (SODA '06, pp. 954-959, 2006). It is known that for this problem no deterministic algorithm can have a competitive better than 2k-1, and that no randomized algorithm can have a competitive ratio better than lnk.
This paper shows that many robust control problems can be formulated as constrained optimization problems and can be tackled by using randomized algorithms. Two different approaches in searching reliable solutions to ...
详细信息
This paper shows that many robust control problems can be formulated as constrained optimization problems and can be tackled by using randomized algorithms. Two different approaches in searching reliable solutions to robustness analysis problems under constraints are proposed, and the minimum computational efforts for achieving certain reliability and accuracy are investigated and bounds for sample size are derived. Moreover, the existing order statistics distribution theory is extended to the general case in which the distribution of population is not assumed to be continuous and the order statistics is associated with certain constraints.
The key objects in the group-theoretic approach to matrix multiplication are subsets of a group satisfying the so-called triple product property (TPP). In this paper, we focus on the problem of efficiently finding the...
详细信息
The key objects in the group-theoretic approach to matrix multiplication are subsets of a group satisfying the so-called triple product property (TPP). In this paper, we focus on the problem of efficiently finding the triple product property triples. We deduce and present some new characteristics of the triple product property. Using these new characteristics, we firstly propose an efficient deterministic algorithm in which a screening process based on historical information is designed to reduce the search space. In contrast to some of the recent heuristic search methods, the proposed deterministic algorithm can search all kinds of TPP triples in a highly efficient way with the help of a novel representation for subsets and a Moving I principle. In addition, we also propose an efficient randomized algorithm for finding TPP triples, which adopts a greedy randomized strategy to randomly generate possible TPP candidates. Experimental results demonstrate that our proposed deterministic algorithm can achieve a huge speed-up in terms of running time compared with the existing deterministic algorithm, and the proposed randomized algorithm outperforms other existing approaches for finding TPP triples. (C) 2018 Elsevier B.V. All rights reserved.
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm ...
详细信息
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.
In this paper, we present some single-pass randomized algorithms to compute LU decomposition. These algorithms need only one pass over the original matrix and hence are very suitable for extremely large and high-dimen...
详细信息
In this paper, we present some single-pass randomized algorithms to compute LU decomposition. These algorithms need only one pass over the original matrix and hence are very suitable for extremely large and high-dimensional matrix stored outside of core memory or generated in a streaming fashion. Rigorous error bounds and complexity of these algorithms are provided. Numerical experiments show that these single-pass algorithms have the similar accuracy and runtime (excluding the cost of matrix transfer) compared with the state-of-the-art randomized algorithms for LU decomposition. (C) 2020 Elsevier Inc. All rights reserved.
In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C 'not equal CofG, and if yes, how quickly? If the input grap...
详细信息
In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C 'not equal CofG, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n vertex graphs with minimum degree delta and maximum degree Delta. We provide a linear-time algorithm for computing a cycle C 'not equal C of length at least n-4 alpha(root n+2 alpha)+8, where alpha = Delta-2 / delta-2. This results provides a constructive proof of a recent result by Girao, Kittipassorn, and Narayanan in the regime of Delta/delta = o(root n). Our second relaxation of the problem is *** propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every 0< p <= 0.02, if the minimum degree of G is at least 8 / p log root 8n + 4, then a second Hamiltonian cycle can be computed with probability at least 1-1 / n(50/p(4)+1)in poly (n)2(4pn )time. This result implies that, when the minimum degree delta is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular,when delta = omega(log n), our probabilistic algorithm works in 2(o(n) )time.
Electric vehicle charging stations (EVCSs) come along with great challenges for the power grid due to their highly uncertain load characteristic. This is particularly the case for charging stations located in nonresid...
详细信息
Electric vehicle charging stations (EVCSs) come along with great challenges for the power grid due to their highly uncertain load characteristic. This is particularly the case for charging stations located in nonresidential areas, such as commercial centers, company sites, or car-rental stations. For a safe and sustainable operation of the power grid, distribution system operators require reliable load forecasts of such charging stations. In this brief, a robust EVCS management strategy is proposed, which provides a day-ahead upper limit profile of the EVCS's power consumption. In real time, this upper limit profile is strictly respected while guaranteeing-at a configurable probability-the Quality of Service. The strategy is based on randomized algorithms and relies on a statistic occupancy model of the EVCS while not requiring any online forecasts of each EVs' arrival and departure schedules. In a case study based on statistic data, which has been provided by the Euref Campus in Berlin, the feasibility and relevance of the proposed approach are demonstrated.
randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-c...
详细信息
randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. First, a mechanism for calculating the approximation error in the Frobenius norm is proposed, which enables efficient adaptive rank determination for a large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by Martinsson and Voronin, this results in an algorithm called randQB_EI. Then, we further revise the algorithm to obtain a pass-efficient algorithm, randQB_FP, which is mathematically equivalent to the existing randQB algorithms and also suitable for the fixed-precision problem. Especially, randQB_FP can serve as a single-pass algorithm for calculating leading singular values, under a certain condition. With large and/or sparse test matrices, we have empirically validated the merits of the proposed techniques, which exhibit remarkable speedup and memory saving over the blocked randQB algorithm. We have also demonstrated that the single-pass algorithm derived by randQB_FP is much more accurate than an existing single-pass algorithm. And with data from a scenic image and an information retrieval application, we have shown the advantages of the proposed algorithms over the adaptive range finder algorithm for solving the fixed-precision problem.
暂无评论