Open Access. Powered by Scholars. Published by Universities.®

Numerical Analysis and Computation Commons™

Open Access. Powered by Scholars. Published by Universities.®

Algorithm

Articles 1 - 6 of 6

Full-Text Articles in Numerical Analysis and Computation

New Algorithmic Support For The Fundamental Theorem Of Algebra, Vitaly Zaderman Feb 2024

New Algorithmic Support For The Fundamental Theorem Of Algebra, Vitaly Zaderman

Dissertations, Theses, and Capstone Projects

Univariate polynomial root-finding is a venerated subjects of Mathematics and Computational Mathematics studied for four millenia. In 1924 Herman Weyl published a seminal root-finder and called it an algorithmic proof of the Fundamental Theorem of Algebra. Steve Smale in 1981 and Arnold Schonhage in 1982 proposed to classify such algorithmic proofs in terms of their computational complexity. This prompted extensive research in 1980s and 1990s, culminated in a divide-and-conquer polynomial root-finder by Victor Pan at ACM STOC 1995, which used a near optimal number of bit-operations. The algorithm approximates all roots of a polynomial p almost as fast as one …

Go to article

New Method For Computing The Euclidean Condition Number With Rim-C, Cody Mccarthy Jan 2024

New Method For Computing The Euclidean Condition Number With Rim-C, Cody Mccarthy

Dissertations, Master's Theses and Master's Reports

The condition number, being critical to solving linear systems, has many impor-
tant applications. Specifically for robust control analysis, the Euclidean norm has
widespread use over the 1-norm and ∞-norm such as determining a control system’s
stability to uncertainty [1]. Much work has been done with estimating the Euclidean
condition number, but current algorithms for computing said condition number, with
large matrices, tend to run slow as well as requiring a large amount of computa-
tional resources. This report seeks to provide a more time efficient algorithm that
utilizes MATLAB’s eigs, svds, and normest commands as well as the recently …

Go to article

Lecture 08: Partial Eigen Decomposition Of Large Symmetric Matrices Via Thick-Restart Lanczos With Explicit External Deflation And Its Communication-Avoiding Variant, Zhaojun Bai Apr 2021

Lecture 08: Partial Eigen Decomposition Of Large Symmetric Matrices Via Thick-Restart Lanczos With Explicit External Deflation And Its Communication-Avoiding Variant, Zhaojun Bai

Mathematical Sciences Spring Lecture Series

There are continual and compelling needs for computing many eigenpairs of very large Hermitian matrix in physical simulations and data analysis. Though the Lanczos method is effective for computing a few eigenvalues, it can be expensive for computing a large number of eigenvalues. To improve the performance of the Lanczos method, in this talk, we will present a combination of explicit external deflation (EED) with an s-step variant of thick-restart Lanczos (s-step TRLan). The s-step Lanczos method can achieve an order of s reduction in data movement while the EED enables to compute eigenpairs in batches along with a number …

Go to article

Yelp’S Review Filtering Algorithm, Yao Yao, Ivelin Angelov, Jack Rasmus-Vorrath, Mooyoung Lee, Daniel W. Engels Aug 2018

Yelp’S Review Filtering Algorithm, Yao Yao, Ivelin Angelov, Jack Rasmus-Vorrath, Mooyoung Lee, Daniel W. Engels

SMU Data Science Review

In this paper, we present an analysis of features influencing Yelp's proprietary review filtering algorithm. Classifying or misclassifying reviews as recommended or non-recommended affects average ratings, consumer decisions, and ultimately, business revenue. Our analysis involves systematically sampling and scraping Yelp restaurant reviews. Features are extracted from review metadata and engineered from metrics and scores generated using text classifiers and sentiment analysis. The coefficients of a multivariate logistic regression model were interpreted as quantifications of the relative importance of features in classifying reviews as recommended or non-recommended. The model classified review recommendations with an accuracy of 78%. We found that reviews …

Go to article

A Simple Linear Time Algorithm For Computing A 1-Median On Cactus Graphs, Kien T. Nguyen, Pham V. Chien, Ly H. Hai, Huynh D. Quoc Jun 2017

A Simple Linear Time Algorithm For Computing A 1-Median On Cactus Graphs, Kien T. Nguyen, Pham V. Chien, Ly H. Hai, Huynh D. Quoc

Applications and Applied Mathematics: An International Journal (AAM)

We address the problem of finding a 1-median on a cactus graph. The problem has already been solved in linear time by the algorithms of Burkard and Krarup (1998), and Lan and Wang (2000). These algorithms are complicated and need efforts. Hence, we develop in this paper a simpler algorithm. First, we construct a condition for a cycle that contains a 1-median or for a vertex that is indeed a 1-median of the cactus. Based on this condition, we localize the search for deriving a 1-median on the underlying cactus. Complexity analysis shows that the approach runs in linear time.

Go to article

Propeller, Joel Kahn Mar 2013

Propeller, Joel Kahn

The Transdisciplinary STEAM+ Journal

This image is based on several different algorithms interconnected within a single program in the language BASIC-256. The fundamental structure involves a tightly wound spiral working outwards from the center of the image. As the spiral is drawn, different values of red, green and blue are modified through separate but related processes, producing the changing appearance. Algebra, trigonometry, geometry, and analytic geometry are all utilized in overlapping ways within the program. As with many works of algorithmic art, small changes in the program can produce dramatic alterations of the visual output, which makes lots of variations possible.

Go to article