Xu Feng, Wenjian Yu, Yuyang Xie et al. · ACM Transactions on Mathematical Software · 2024
Aiming to provide a faster and convenient truncated SVD algorithm for large sparse matrices from real applications (i.e., for computing a few of the largest singular values and the corresponding singular vectors), a dynamically shifted power iteration technique is applied to improve the accuracy of the randomized SVD method. This results in a d yn a mic sh ifts-based randomized SVD (dashSVD) algorithm, which also collaborates with the skills for handling sparse matrices. An accuracy-control mechanism is included in the dashSVD algorithm to approximately monitor the per vector error bound of computed singular vectors with negligible overhead. Experiments on real-world data validate that the dashSVD algorithm largely improves the accuracy of a randomized SVD algorithm or attains the same accuracy with fewer passes over the matrix, and provides an efficient accuracy-control mechanism to the randomized SVD computation, while demonstrating the advantages on runtime and parallel efficiency. A bound of the approximation error of the randomized SVD with the shifted power iteration is also proved.
Cited by 7Open access
Sofiia Shvaiko, Longxiu Huang, Elizaveta Rebrova · arXiv (Cornell University) · 2026
Randomized Kaczmarz (RK) is a simple and fast solver for consistent overdetermined systems, but it is known to be fragile under noise. We study overdetermined $m\times n$ linear systems with a sparse set of corrupted equations, $ {\bf A}{\bf x}^\star = {\bf b}, $where only $\tilde{\bf b} = {\bf b} + \boldsymbol{\varepsilon}$ is observed with $\|\boldsymbol{\varepsilon}\|_0 \le βm$. The recently introduced QuantileRK (QRK) algorithm addresses this issue by testing residuals against a quantile threshold, but computing a per-iteration quantile across many rows is costly. In this work we (i) reanalyze QRK and show that its convergence rate improves monotonically as the corruption fraction $β$ decreases; (ii) propose a simple online detector that flags and removes unreliable rows, which reduces the effective $β$ and speeds up convergence; and (iii) make the method practical by estimating quantiles from a small random subsample of rows, preserving robustness while lowering the per-iteration cost. Simulations on imaging and synthetic data demonstrate the efficiency of the proposed method.
Cited by 0Open access
Zhen Xiao , Kenneth P. Birman · 2008
An efficient error recovery algorithm is essential for reliable multicast in large groups. Tree-based protocols (RMTP, TMTP, LBRRM) group receivers into local regions and select a repair server for performing error recovery in each region. Hence a single server bears the entire responsibility of error recovery for a region. In addition, the deployment of repair servers requires topological information of the underlying multicast tree, which is generally not available at the transport layer. This paper presents RRMP, a randomized reliable multicast protocol which improves the robustness of tree-based protocols by diffusing the responsibility of error recovery among all members in a group. The protocol works well within the existing IP multicast framework and does not require additional support from routers. Both analysis and simulation results show that the performance penalty due to randomization is low and can be tuned according to application requirements.
Cited by 0
Ankur Pariyani, Abhigyan Gupta, Pallab Ghosh · Computers & Chemical Engineering · 2006
Cited by 51
Vartan, Farrokh, Williams, Colin · NASA Technical Reports Server (NASA)
A biased randomized algorithm has been developed to enable the rapid computational solution of a propositional- satisfiability (SAT) problem equivalent to a diagnosis problem. The closest competing methods of automated diagnosis are described in the preceding article "Fast Algorithms for Model-Based Diagnosis" and "Two Methods of Efficient Solution of the Hitting-Set Problem" (NPO-30584), which appears elsewhere in this issue. It is necessary to recapitulate some of the information from the cited articles as a prerequisite to a description of the present method. As used here, "diagnosis" signifies, more precisely, a type of model-based diagnosis in which one explores any logical inconsistencies between the observed and expected behaviors of an engineering system. The function of each component and the interconnections among all the components of the engineering system are represented as a logical system. Hence, the expected behavior of the engineering system is represented as a set of logical consequences. Faulty components lead to inconsistency between the observed and expected behaviors of the system, represented by logical inconsistencies. Diagnosis - the task of finding the faulty components - reduces to finding the components, the abnormalities of which could explain all the logical inconsistencies. One seeks a minimal set of faulty components (denoted a minimal diagnosis), because the trivial solution, in which all components are deemed to be faulty, always explains all inconsistencies. In the methods of the cited articles, the minimal-diagnosis problem is treated as equivalent to a minimal-hitting-set problem, which is translated from a combinatorial to a computational problem by mapping it onto the Boolean-satisfiability and integer-programming problems. The integer-programming approach taken in one of the prior methods is complete (in the sense that it is guaranteed to find a solution if one exists) and slow and yields a lower bound on the size of the minimal diagnosis. In contrast, the present approach is incomplete and fast and yields an upper bound on the size of the minimal diagnosis.
Cited by 0Open access
Abdelaaziz El Hibaoui, Yves Métivier, J. M. Robson et al. · HAL (Le Centre pour la Communication Scientifique Directe) · 2008
International audience
Cited by 6
Kutz, M., Schweitzer, P. · MPG.PuRe (Max Planck Society) · 2006
We present a novel randomized approach to the graph isomorphism problem. Our \nalgorithm aims at solving difficult instances by producing randomized \ncertificates for \\emph{non}-isomorphism. We compare our implementation to the \nde facto standard nauty. On many of the hardest known instances, the incidence \ngraphs of finite projective planes, our program is considerably faster than \nnauty.\n However, it is inherent to our approach that it performs better on pairs of \nnon-isomorphic graphs than on isomorphic instances.\n\nOur algorithm randomly samples substructures in the given graphs in order to \ndetect dissimilarities between them. The choice of the sought-after structures \nas well as the tuning of the search process is dynamically adapted during the \nsampling. Eventually, a randomized certificate is produced by which the user \ncan verify the non-isomorphism of the input graphs. As a byproduct of our \napproach, we introduce a new concept of regularity for graphs which is meant to \ncapture the computational hardness of isomorphism problems on graphs.
Cited by 0Open access
Komal Pandya, Abyayananda Maiti · Research Square · 2023
Abstract We study a randomized 1/e-competitive ε-RANKING algorithm for the onlinetrichromatic matching problem. This problem involves finding matching in tripartite graphs having three disjoint sets of vertices. Our model encompasses a tripartite graph configuration, where an offline vertex set is an intermediary connecting two opposing sets. The vertices from the latter sets unfold online, arriving individually over time. ε-RANKING employs a randomization strategy where offline vertices are assigned random ranks between [0, 1]. It extends the idea of finding the lowest-ranked neighbor of the newly arrived online vertex presented by Karp et al. [1] in their RANKING algorithm. This approach exploits the principles of RANKING and matching from the domain of online bipartite matching to the more complex context of online trichromatic matching.
Cited by 1Open access
David Eppstein · 2000
Cited by 0
Zhen Xiao, Ken Birman · 2002
An efficient error recovery algorithm is essential for a liable multicast in large groups. Tree-based protocols (RMTP, TMTP, LBRRM) group receivers into local regions and select a repair server for performing error recovery in each region. Hence a single server bears the entire responsibility of error recovery for a region. In addition, the deployment of repair servers requires topological information of the underlying multicast tree, which is generally not available at the transport layer. This paper presents RRMP, a randomized reliable multicast protocol which improves the robustness of tree-based protocols by diffusing the responsibility of error recovery among all members in a group. The protocol works well within the existing IP multicast framework and does not require additional support from routers. Both analysis and simulation results show that the performance penalty due to randomization is low and can be tuned according to application requirements.
Cited by 31
Sam Gunn, Ramis Movassagh · Lecture notes in computer science · 2025
Cited by 2Open access
Parth Shah, Uzair Faquih, Rutuja Dhanaji Devkar et al. · Zenodo (CERN European Organization for Nuclear Research) · 2022
This is a problematic era because of the boom in the subject of advanced technology and the demand we are dealing with nowadays. Therefore, examinations рlаy а сruсiаl rоle in сheсking оut аn individual's performance, аnd рreраrаtiоn оf exаm questiоn рарers hаs соnsistently been а mаtter оf interest. And this is why it's far critical to have an intelligent system for the growth of students in addition to checking their learning skills, thereby retaining a check on student performance. Faculties generate various question papers in keeping with the university's assessment requirements. It's very challenging for the teachers to make question papers with multiple questions that meet the course's learning targets. We have рrороsed аn аutоmаted рrосess оf question рарer generation thаt is fast, streamlined, randomized, and secure. Every action executed task by the system is automated, so that storage space, bias, and security are not a challenge anymore. It automatically creates a variety of sets of questions now and then without worrying about replication and duplication from the initial exam at the same time as the question bank keeps growing.
Cited by 0Open access
Marcin Baranek, Andrzej Kałuża, Paweł Morkisz et al. · Journal of Computational and Applied Mathematics · 2025
Cited by 0
Rasmus Bo Hasselbalch, Louis Lind Plesner, Mia Marie Pries‐Heje et al. · Scandinavian Journal of Trauma Resuscitation and Emergency Medicine · 2016
Cited by 10Open access
Laura Cecchi · El Servicio de Difusión de la Creación Intelectual (National University of La Plata) · 1997
In spite of the NP-completeness of the satisfiability decision problem (SAT problem), many researchers have been attracted by it because SAT has many applications in Artificial Intelligence. This paper presents a randomized David-Putnam based algorithm (RSAT) which solves this problem. Instead of selecting the next literal to be set true or false through a heuristic selection rule, RSAT does it through a random algorithm. RSAT not only improves the well-know Davis-Putnam Procedure that has been implemented with a heuristic selection rule, but avoids the incompleteness problem of the local search algorithms as well. RSAT is described in detail and it is compared with the heuristic based Davis-Putnam algorithm HDPP. We discuss the main features of the RSAT implementation and we especially analyze the random number generator features. Although the scope of the experiment is bound by the number of variables, our results indicate that the heuristic can be guessed by a random number generator and even improved. Empirical analysis that support the final conclusions are shown.
Cited by 0Open access
Lunshan Gao · Research Square · 2023
Abstract This paper describes a new randomized algorithm for calculating local maximum cuts of the maximum cut problems in graph theory. The new algorithm transforms the maximum cut problem into a new form by using fuzzy logic technique. The transformation enables the algorithm to use the first-order derivative method to find optimal values for discrete non-linear optimization problems. This paper proves that the solution of the new algorithm satisfies the ϵ−δ condition. The algorithm converts decimal solution points to integer solution points by using the defuzzification technique. This paper also proves that the defuzzification maintains the local maximum value. The new algorithm is compared with IBM ILOG CPLEX. The numerical experiments indicate that the performance of the new algorithm is better than that of IBM ILOG CPLEX for finding local maximum cuts.
Cited by 0Open access
Nikhil Bansal, Niv Buchbinder, Joseph Naor · Journal of the ACM · 2012
We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O (log k )-competitive online algorithm for this problem, where k is the cache size. This is the first randomized o ( k )-competitive algorithm and its competitive ratio matches the known lower bound for the problem, up to constant factors. More generally, we design an O (log( k /( k − h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and it is compared to an optimal offline solution with cache size h ≤ k . Our solution is based on a two-step approach. We first obtain an O (log k )-competitive fractional algorithm based on an online primal-dual approach. Next, we obtain a randomized algorithm by rounding in an online manner the fractional solution to a probability distribution on the possible cache states. We also give an online primal-dual randomized O (log N )-competitive algorithm for the Metrical Task System problem (MTS) on a weighted star metric on N leaves.
Cited by 73
Xu Feng, Wenjian Yu, Yuyang Xie et al. · arXiv (Cornell University) · 2024
Aiming to provide a faster and convenient truncated SVD algorithm for large sparse matrices from real applications (i.e. for computing a few of largest singular values and the corresponding singular vectors), a dynamically shifted power iteration technique is applied to improve the accuracy of the randomized SVD method. This results in a dynamic shifts based randomized SVD (dashSVD) algorithm, which also collaborates with the skills for handling sparse matrices. An accuracy-control mechanism is included in the dashSVD algorithm to approximately monitor the per vector error bound of computed singular vectors with negligible overhead. Experiments on real-world data validate that the dashSVD algorithm largely improves the accuracy of randomized SVD algorithm or attains same accuracy with fewer passes over the matrix, and provides an efficient accuracy-control mechanism to the randomized SVD computation, while demonstrating the advantages on runtime and parallel efficiency. A bound of the approximation error of the randomized SVD with the shifted power iteration is also proved.
Cited by 0Open access
А. И. Жданов, Yury Vyacheslavovich Sidorov · Computer Optics · 2015
The article describes the parallel implementation of a randomized regularized Kaczmarz's algorithm. By way of illustration, the randomized parallel version of the algorithm is used for solving the Fredholm integral equation of the first kind with a perturbed right-hand side, showing that in this way the computation speed can be increased up to 4 times as compared to the sequential randomized version.
Cited by 8Open access
Bogdan Dumitrescua B · 2014
Cited by 0