New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:15, 15 February 2023 Revuz's algorithm (Acyclic DFA Minimization DFA Minimization) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/pii/0304397592901423")
- 11:15, 15 February 2023 Almeida & Zeitoun (Cyclic Nontrivial SCCs DFA Minimization DFA Minimization) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf")
- 11:15, 15 February 2023 Brzozowski's algorithm (DFA Minimization DFA Minimization) (hist | edit) [526 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({2}^n)$ words (http://www.cs.ru.nl/bachelors-theses/2017/Erin_van_der_Veen___4431200___The_Practical_Performance_of_Automata_Minimization_Algorithms.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1963 == Reference == https://www.semanticscholar.org/paper/Canonical-regular-expressions-and-minimal-state-for-...")
- 11:15, 15 February 2023 Moore's algorithm (DFA Minimization DFA Minimization) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n)$ words (Derived: Auxiliary data structure that keeps track of a 'block' binary variable for each state) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://doi.org/10.2307/2964500")
- 11:15, 15 February 2023 Hopcroft's algorithm (DFA Minimization DFA Minimization) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn \log n)$ == Space Complexity == $O(kn)$ words (https://link.springer.com/content/pdf/10.1007/3-540-54430-5_107.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://www.cs.cmu.edu/~./sutner/CDM/papers/Hopcroft71.pdf")
- 11:15, 15 February 2023 Dekel; Nassimi & Sahni Parallel Implementation (Topological Sorting Topological Sorting) (hist | edit) [652 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( log² V)$ == Space Complexity == $O(V^{2})$?? words (Their n*n*n cube setup seems to only require each processor to keep track of one entry A(i, j), B(i, j) and propagates the results across the structure, only requiring O(1) auxiliary space per processor. Comparison sorting can be done easily with O(1) auxiliary space per processor.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Comp...")
- 11:15, 15 February 2023 Tarjan's DFS based algorithm (Topological Sorting Topological Sorting) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ auxiliary? words (maintain O(V)-sized recursion stack, along with O(V) marks) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://link.springer.com/article/10.1007/BF00268499")
- 11:15, 15 February 2023 Kahn's algorithm (Topological Sorting Topological Sorting) (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ auxiliary words (maintain stack of nodes with no incoming edges) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == https://dl.acm.org/doi/10.1145/368996.369025")
- 11:15, 15 February 2023 Chan's algorithm Parallel Implementation ( Variance Calculations) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O({1})$ per processor words (Each processor maintains O(1) information related to count, mean, M2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW(??) PRAM == Year == 1979 == Reference == http://i.stanford.edu/pub/cstr/reports/cs/tr/79/773/CS-TR-79-773.pdf")
- 11:15, 15 February 2023 Welford's Online algorithm ( Variance Calculations) (hist | edit) [420 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintains O(1) information (count, mean, M2) that is constantly updated as values are read) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1962 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.302.7503&rep=rep1&type=pdf")
- 11:15, 15 February 2023 Weighted incremental algorithm ( Variance Calculations) (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintains O(1) information (sum of weights, sum of squared weights, weighted sum of values, weighted sum of values squared) that is constantly updated as values are read) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference == https://dl.acm.org/doi/10.1145/359146.359153")
- 11:15, 15 February 2023 Two-pass algorithm ( Variance Calculations) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintain number of values, sum of values, and sum of squares of (value minus mean) terms) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Naïve algorithm ( Variance Calculations) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintain number of values, sum of values, and sum of squares of values) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Bowyer–Watson algorithm (Voronoi Diagrams Voronoi Diagrams) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ auxiliary words (Computes the Delaunay triangulation first (O(n) space), then uses that to generate the Voronoi diagram) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1981 == Reference == https://academic.oup.com/comjnl/article/24/2/167/338200")
- 11:15, 15 February 2023 Linde–Buzo–Gray algorithm ( Voronoi Diagrams) (hist | edit) [291 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/1094577/")
- 11:15, 15 February 2023 Fortune's algorithm (Voronoi Diagrams Voronoi Diagrams) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ auxiliary words (https://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == http://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf")
- 11:15, 15 February 2023 Kong and Wilken Algorithm (Global Register Allocation Register Allocation) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == ? Probably also dependent on the ILP solver () == Description == Integer programming for irregular register architectures == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://dl.acm.org/doi/10.5555/290940.291002")
- 11:15, 15 February 2023 Optimal Register Allocation (ORA), Goodwin & Wilken Algorithm (Global Register Allocation Register Allocation) (hist | edit) [478 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == Depends on the choice of {0}-{1} ILP solver ("Memory usage is dominated by the usage of the integer program solver.") == Description == 0-1 integer linear programming problem == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-024X%28199608%2926%3A8%3C929%3A%3AA...")
- 11:15, 15 February 2023 Cooper and Dasgupta algorithm ( Register Allocation) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference ==")
- 11:15, 15 February 2023 Linear Scan, Poletto & Sarkar (Global Register Allocation Register Allocation) (hist | edit) [471 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(r)$ words (Derived: given the live ranges, the only auxiliary data structure is an "active" list that contains the active live ranges and this has length at most $r$) == Description == Greedy assignment == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf")
- 11:15, 15 February 2023 Chow's Algorithm (Global Register Allocation Register Allocation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm also uses a register interference graph (RIG)) == Description == Assumes all variables allocated in main memory (i.e. assumes no spill handling required). Priority-based RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/502874.50...")
- 11:15, 15 February 2023 Chaitin's Algorithm (Global Register Allocation Register Allocation) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm uses both an adjacency matrix (called the bit matrix) and adjacency lists (called the adjacency vectors)) == Description == RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://dl.acm.org/doi/10.1145/872726.806984")
- 11:15, 15 February 2023 Bottom-m sketches streaming algorithm (streaming Cardinality Estimation) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(m)$ words (only keep track of m minimum values. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
- 11:15, 15 February 2023 Min/max sketches streaming algorithm (streaming Cardinality Estimation) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O({1})$ words (only keep track of minimum value. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
- 11:15, 15 February 2023 HyperLogLog algorithm ( Cardinality Estimation) (hist | edit) [417 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words (https://oertl.github.io/hyperloglog-sketch-estimation-paper/paper/paper.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2007 == Reference == http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf")
- 11:15, 15 February 2023 HyperLogLog++ ( Cardinality Estimation) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words ((see hyperloglog?)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2014 == Reference == https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf")
- 11:15, 15 February 2023 LogLog algorithm ( Cardinality Estimation) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log(log(n)$)) words (http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2003 == Reference == http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf")
- 11:15, 15 February 2023 Flajolet–Martin algorithm ( Cardinality Estimation) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log n)$ words (https://www.sciencedirect.com/science/article/pii/S0022000097915452) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1984 == Reference == http://algo.inria.fr/flajolet/Publications/src/FlMa85.pdf")
- 11:15, 15 February 2023 Naive solution ( Cardinality Estimation) (hist | edit) [302 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(n)$ words (keep track of exact histogram, may require storing all values) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Generalized expectation maximization (GEM) algorithm ( Maximum Likelihood Parameters) (hist | edit) [485 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4} log^{0.{1}.5}n)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1994 == Reference == https://web.eecs.umich.edu/~fessler/papers/files/jour/94/web/fessler-94-...")
- 11:15, 15 February 2023 Α-EM algorithm ( Maximum Likelihood Parameters) (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of alpha-log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1109/TIT.2002.808105")
- 11:15, 15 February 2023 Expectation conditional maximization (ECM) ( Maximum Likelihood Parameters) (hist | edit) [427 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://arxiv.org/abs/1709.06970")
- 11:15, 15 February 2023 Parameter-expanded expectation maximization (PX-EM) algorithm ( Maximum Likelihood Parameters) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta (+ alpha) and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1998 == Reference == https://www.jstor.org/stable/2337481")
- 11:15, 15 February 2023 Newton–Raphson algorithm ( Maximum Likelihood Parameters) (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r^{2})$? words (Stores current theta guess, which is updated each iteration, and requires computation of the (inverse of the) Hessian matrix. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1685 == Reference == -")
- 11:15, 15 February 2023 Knuth–Bendix algorithm (General Groups (uncompleted?) Coset Enumeration) (hist | edit) [462 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.5}^n n^{2} logn)$ == Space Complexity == $O(ng)$??? words (Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1970 == Reference == https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf")
- 11:15, 15 February 2023 Expectation–maximization (EM) algorithm ( Maximum Likelihood Parameters) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://www.jstor.org/stable/2984875")
- 11:15, 15 February 2023 Todd–Coxeter algorithm (Bounded Subgroup Index Coset Enumeration) (hist | edit) [501 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(gkc)$ words (Defines O(k) tables, each with O(g) columns and O(c) rows) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1936 == Reference == https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/practical-method-for-enumerating-cosets-of-a-finite-abstract-group/030657...")
- 11:15, 15 February 2023 Haselgrove; Leech and Trotter (Bounded Subgroup Index Coset Enumeration) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(ng)$? words (Implementation stores a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
- 11:15, 15 February 2023 Muller's method (General Root Computation Root Computation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1956 == Reference == https://www.jstor.org/stable/200...")
- 11:15, 15 February 2023 Ridder's method (General Root Computation Root Computation) (hist | edit) [478 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference == https://ieeexplore.ieee.org/document/1084580/")
- 11:15, 15 February 2023 Secant method (General Root Computation Root Computation) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Newton's method (Root Computation with continuous first derivative Root Computation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate $x_i$ and the derivative $f'$ (assuming this takes $O(1)$ space); iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Referenc...")
- 11:15, 15 February 2023 Halley's method (Root Computation with continuous second derivative Root Computation) (hist | edit) [482 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate x_i and the derivatives f' and f'' (assuming this takes O(1) space); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference...")
- 11:15, 15 February 2023 False position method (General Root Computation Root Computation) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1690 == Reference == -")
- 11:15, 15 February 2023 Bisection method (General Root Computation Root Computation) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1820 == Reference == -")
- 11:15, 15 February 2023 MRRR algorithm (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words (Need to compute and store some matrix of the form $(A-mu*I)^{(-1)}$ (for inverse iteration-like uses)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1999 == Reference == https://www.cs.utexas.edu/users/inderjit/public_papers/DesignMRRR_toms06.pdf")
- 11:15, 15 February 2023 Homotopy method (All eigenpairs; Eigenpair closest to mu; Any eigenpair; Any eigenvalue; All eigenvalues Eigenvalues (Iterative Methods)) (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$?? words (Conservative bound on space used per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://www.scirp.org/(S(czeh2tfqyw2orz553k1w0r45))/reference/ReferencesPapers.aspx?ReferenceID=530065")
- 11:15, 15 February 2023 Folded spectrum method (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of O(n)-sized vectors per iteration; matrix-to-vector multiplication only requires O(n) aux space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1934 == Reference == https://journals.aps.org/pr/abstract/10.1103/PhysRev.46.828")
- 11:15, 15 February 2023 Divide-and-conquer (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [411 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n^{2})$ words (Stores reduction to tridiagonal form; recursion (S(n)=2S(n/2)+O(n^2)) should work out to O(n^2)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == https://link.springer.com/content/pdf/10.1007/BF01389480.pdf")
- 11:15, 15 February 2023 Jacobi eigenvalue algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computes and stores results of GSG^T iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1846 == Reference == https://gdz.sub.uni-goettingen.de/id/PPN243919689_0030")