User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 11:1511:15, 15 February 2023 diff hist +347 N Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (Derived: You only need a constant number of variables that are of $O(1)$ size at any given time) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1965 == Reference == -" current
- 11:1511:15, 15 February 2023 diff hist +406 N Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1965 == Reference == https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf"
- 11:1511:15, 15 February 2023 diff hist +404 N Fleury's algorithm + Thorup (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) Created page with "== Time Complexity == $O(E log^{3}(E)$ loglogE) == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf"
- 11:1511:15, 15 February 2023 diff hist +308 N Hierholzer's algorithm (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1873 == Reference == -" current
- 11:1511:15, 15 February 2023 diff hist +401 N Fleury's algorithm + Tarjan (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) Created page with "== Time Complexity == $O(E^{2})$ == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://collaborate.princeton.edu/en/publications/a-note-on-finding-the-bridges-of-a-graph" current
- 11:1511:15, 15 February 2023 diff hist +268 N Mucha and Sankowski ( Maximum-Weight Matching) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference == https://dl.acm.org/doi/10.1109/FOCS.2004.40" current
- 11:1511:15, 15 February 2023 diff hist +274 N Micali; Vazirani ( Maximum-Weight Matching) Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/4567800"
- 11:1511:15, 15 February 2023 diff hist +418 N Edmonds (Maximum-Weight Matching Maximum-Weight Matching) Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn^{2})$?? words (At worst, keeps track of the entire sequence of graphs created; it's possible this can be improved?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf" current
- 11:1511:15, 15 February 2023 diff hist +368 N Lipton; Mehta (2-player Nash Equilibria) Created page with "== Time Complexity == $O(n^{(O(log n)$)} (previously $O(n^{2} logn)$????) == Space Complexity == (see sheet {2}) words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933" current
- 11:1511:15, 15 February 2023 diff hist +464 N Hungarian algorithm (Bipartite Maximum-Weight Matching Maximum-Weight Matching) Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{2})$ words (Either graph interpretation maintains O(n^2) orientations and O(n) potential or matrix interpretation manipulates an O(n)*O(n) auxiliary matrix) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1955 == Reference == https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf" current
- 11:1511:15, 15 February 2023 diff hist +347 N Lemke–Howson algorithm (2-player Nash Equilibria) Created page with "== Time Complexity == {2}^{($O(n+m)$)} (previously $O(n^{4})$????) == Space Complexity == $O(mn)$? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://epubs.siam.org/doi/abs/10.1137/0112033?journalCode=smjmap.1" current
- 11:1511:15, 15 February 2023 diff hist +502 N De Prisco (Approximate OBST Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary probability distribution, and three phases that alter a single tree that eventually is the result) == Description == == Approximate? == Approximate Approximation Factor: Upper bound: $H + 1 - p_0 - p_n + p_{max}$ == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.sciencedirect.com/science/a..." current
- 11:1511:15, 15 February 2023 diff hist +402 N Levcopoulos; Lingas; Sack (Approximate OBST Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary list of initial size $4n$) == Description == == Approximate? == Approximate Approximation Factor: $1 + \epsilon$ == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0304397589901345" current
- 11:1511:15, 15 February 2023 diff hist +310 N Yao (OBST Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://doi.org/10.1137/0603055) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://doi.org/10.1137/0603055" current
- 11:1511:15, 15 February 2023 diff hist +412 N Naive algorithm (OBST Optimal Binary Search Trees) Created page with "== Time Complexity == $O({4}^n /n \sqrt{n})$ == Space Complexity == $O({1})$ words (Derived: Constant space to verify optimality. Constant space if you can enumerate the trees in-situ.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == https://www.cs.bgu.ac.il/~michaluz/seminar/Knuth71.pdf" current
- 11:1511:15, 15 February 2023 diff hist +362 N Knuth's DP algorithm (OBST Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4492658) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.cs.bgu.ac.il/~michaluz/seminar/Knuth71.pdf" current
- 11:1511:15, 15 February 2023 diff hist +362 N Modified Knuth's DP algorithm (OBST Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4492658) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.cs.bgu.ac.il/~michaluz/seminar/Knuth71.pdf" current
- 11:1511:15, 15 February 2023 diff hist +331 N Hu–Tucker algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n)$ words (https://epubs.siam.org/doi/10.1137/0121057) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://epubs.siam.org/doi/10.1137/0121057" current
- 11:1511:15, 15 February 2023 diff hist +371 N Garsia–Wachs algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n)$ words (https://epubs.siam.org/doi/epdf/10.1137/0206045, See implementation of MINTREE) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://epubs.siam.org/doi/abs/10.1137/0206045" current
- 11:1511:15, 15 February 2023 diff hist +357 N Heap's algorithm (All Permutations All Permutations) Created page with "== Time Complexity == $O(n)$ per permutation == Space Complexity == $O(n)$ auxiliary words ($O(n)$-sized stack or array necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1963 == Reference == https://academic.oup.com/comjnl/article/6/3/293/360213"
- 11:1511:15, 15 February 2023 diff hist +370 N Tompkins–Paige algorithm (All Permutations All Permutations) Created page with "== Time Complexity == $O(n)$ on specific permutations == Space Complexity == $O(n)$ auxiliary words (Keeps track of auxiliary counting array) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://mathscinet.ams.org/mathscinet-getitem?mr=0080380"
- 11:1511:15, 15 February 2023 diff hist +430 N Steinhaus–Johnson–Trotter algorithm (All Permutations All Permutations) Created page with "== Time Complexity == $O(n)$ on specific permutations == Space Complexity == $O({1})$ auxiliary words (Determining $x_i$ and $y_i$ each iteration can be done in constant space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1963 == Reference == https://www.ams.org/journals/mcom/1963-17-083/S0025-5718-1963-0159764-2/home.html"
- 11:1511:15, 15 February 2023 diff hist +425 N SMAWK algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix) Created page with "== Time Complexity == $O(n({1}+log(n/m)$)) == Space Complexity == $O(n)$ auxiliary? words (Need to keep track of which columns aren't pruned. Also uses $O(n)$ auxiliary space during prune-and-search?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840359"
- 11:1511:15, 15 February 2023 diff hist +388 N Naive algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix) Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O({1})$ auxiliary words (Only needs to keep track of current minimum in current row - once done with a row, can send stored minimum to output and recycle space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -"
- 11:1511:15, 15 February 2023 diff hist +478 N Faugère F5 algorithm (Gröbner Bases Gröbner Bases) Created page with "== Time Complexity == $O(C(n+D_reg, D_reg)$^{\omega}) where omega is the exponent on matrix multiplication == Space Complexity == $O(C(n+D_{reg}, D_{reg})$^{2})? words (Seems to keep track of a square matrix (for monomials) of size $O(C(n+D_{reg}, D_{reg})^2$)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://dl.acm.org/doi/10.1145/780506.780516"
- 11:1511:15, 15 February 2023 diff hist +496 N Faugère F4 algorithm (Gröbner Bases Gröbner Bases) Created page with "== Time Complexity == $O(C(n+D_reg, D_reg)$^{\omega}) where omega is the exponent on matrix multiplication == Space Complexity == $O(C(n+D_{reg}, D_{reg})$^{2})? words (Seems to keep track of a square matrix (for monomials) of size $O(C(n+D_{reg}, D_{reg})^2$)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://linkinghub.elsevier.com/retrieve/..."
- 11:1511:15, 15 February 2023 diff hist +401 N Buchberger's algorithm (Gröbner Bases Gröbner Bases) Created page with "== Time Complexity == d^{({2}^{(n+o({1})})}) == Space Complexity == d^{({2}^{(n+o({1}))})}?? words (Output may contain that many elements. However, this bound seems very crude/loose) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/1088216.1088219" current
- 11:1511:15, 15 February 2023 diff hist +324 N Dual subgradients and the drift-plus-penalty method (Stochastic optimization Convex Optimization (Non-linear)) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(Vmn)$???? words (involves minimizing an expression with up to O(Vmn) terms per iteration?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1993 == Reference ==" current
- 11:1511:15, 15 February 2023 diff hist +376 N Subgradient method (General, Constrained optimization Convex Optimization (Non-linear)) Created page with "== Time Complexity == $O(n^{2} )$ == Space Complexity == $O(n+L)$? words (keep track of current guess x^{(k)}, and needs to compute subgradient g^{(k)}) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1981 == Reference == https://www.springer.com/gp/book/9783642821202" current
- 11:1511:15, 15 February 2023 diff hist +381 N Ellipsoid method (General, Constrained optimization Convex Optimization (Non-linear)) Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(nmL)$ words (see orginal paper (noting that O(alpha*log(H*alpha)) = O(L))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0041555380900610"
- 11:1511:15, 15 February 2023 diff hist +413 N Wolfe; Lemaréchal; Kiwiel (General, Constrained optimization Convex Optimization (Non-linear)) Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n+L)$?? words (keeps track of current guess x^{(k)}, and computes bundle G^{(k)}, direction d^{(k)}, and scalar t^{(k)}?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://link.springer.com/content/pdf/10.1007/BFb0120703.pdf" current
- 11:1511:15, 15 February 2023 diff hist +431 N Gomory's cutting method (ILP;MILPs Convex Optimization (Non-linear)) Created page with "== Time Complexity == $O({2}^n*poly(n, m)$)? (previously $O(n^{3})$) == Space Complexity == $O(nm+m^{2})$ words (See simplex algorithm, but also O(m) variables and constraints are introduced) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1953 == Reference == https://www.cs.uleth.ca/~benkoczi/OR/read/cutting-stock-LP.pdf" current
- 11:1511:15, 15 February 2023 diff hist +321 N Sattolo's algorithm (Cyclic Permutations Generating Random Permutations) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Essentially in-situ) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0020019086900736" current
- 11:1511:15, 15 February 2023 diff hist +295 N Durstenfeld's Algorithm 235 (General Permutations Generating Random Permutations) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Essentially in-situ) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1964 == Reference == https://dl.acm.org/doi/10.1145/364520.364540" current
- 11:1511:15, 15 February 2023 diff hist +411 N Fisher–Yates/Knuth shuffle (General Permutations Generating Random Permutations) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Need to keep track of which elements have been struck out already) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1938 == Reference == https://www.worldcat.org/title/statistical-tables-for-biological-agricultural-and-medical-research/oclc/14222135" current
- 11:1511:15, 15 February 2023 diff hist +408 N Gosper's algorithm ( Cycle Detection) Created page with "== Time Complexity == $O((\lambda + \mu)$ log(\lambda + \mu) t_f) == Space Complexity == \Theta(log(\mu + \lambda)) (https://en.wikipedia.org/wiki/Cycle_detection#Gosper's_algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1978 == Reference == https://www.inwap.com/pdp10/hbaker/hakmem/flows.html#item132" current
- 11:1511:15, 15 February 2023 diff hist +336 N Brent's algorithm ( Cycle Detection) Created page with "== Time Complexity == $O((\lambda + \mu)$ t_f) == Space Complexity == $O({1})$ Pointer algo (Algorithmic Cryptanalysis) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1973 == Reference == https://maths-people.anu.edu.au/~brent/pd/rpb005.pdf" current
- 11:1511:15, 15 February 2023 diff hist +338 N Floyd's tortoise and hare algorithm ( Cycle Detection) Created page with "== Time Complexity == $O((\lambda + \mu)$ t_f) == Space Complexity == $O({1})$ Pointer algo (Algorithmic Cryptanalysis) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1967 == Reference == http://pds7.egloos.com/pds/200801/07/29/p636-floyd.pdf" current
- 11:1511:15, 15 February 2023 diff hist +473 N Naive Implementation (Exact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n^{2})$ Word RAM (Derived: The Leibniz formula for the determinant of the Laplacian can be computed with constant space. The adjugate matrix of the Laplacian takes $n^2$ space.) == Description == Explicitly calculating the inverse of the Laplacian to solve for x == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -" current
- 11:1511:15, 15 February 2023 diff hist +493 N Daitch; Spielman (Inexact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $O(n^{5/4} (log^{2} (n)$ loglogn)^{3/4} log({1}/ϵ)) == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary sparse Cholesky decomposition which has $O(n)$ non-zero entries) == Description == Support Theory (Trusses and Stiffness Matrices) == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://arxiv...."
- 11:1511:15, 15 February 2023 diff hist +513 N Lee; Peng; Spielman (Inexact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary sparse Cholesky decomposition which has $O(n)$ non-zero entries) == Description == Recursive algorithm with sparse Cholesky factorization of Laplacian == Approximate? == Approximate Approximation Factor: The sparse Cholesky decomposition is a 2-approximation == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference..." current
- 11:1511:15, 15 February 2023 diff hist +426 N Kelner; Orecchia; Sidford; Zhu (Inexact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $O(m log^{2} (n)$ loglogn) == Space Complexity == $O(n)$ words (Derived: Uses a spanning tree of the graph that the Laplacian is for) == Description == Low-stretch spanning tree == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://arxiv.org/pdf/1301.6628.pdf"
- 11:1511:15, 15 February 2023 diff hist +317 N Briggs; Henson; McCormick ( SDD Systems Solvers) Created page with "== Time Complexity == $O(n^{1.{2}5} loglogn)$ == Space Complexity == () == Description == Multigrid == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == http://www.math.ust.hk/~mamu/courses/531/tutorial_with_corrections.pdf"
- 11:1511:15, 15 February 2023 diff hist +431 N Blelloch; Koutis; Miller; Tangwongsan (Inexact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == m + $O(n/log n)$ words (https://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/jkoutis/papers/SC10-paper.pdf) == Description == Combinatorial multigrid == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://ieeexplore.ieee.org/document/5644892"
- 11:1511:15, 15 February 2023 diff hist 0 Koutis; Miller and Peng (Inexact Laplacian Solver SDD Systems Solvers) No edit summary
- 11:1511:15, 15 February 2023 diff hist +443 N Koutis; Miller and Peng (Inexact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $\tilde{O}(m log n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary chain of graphs, which can be kept track of with a single spanning tree) == Description == Incremental sparsifier == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://arxiv.org/abs/1102.4842"
- 11:1511:15, 15 February 2023 diff hist +451 N Boman; Chen; Hendrickson; Toledo (Inexact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $O(n log({1}/ϵ)$ ) == Space Complexity == $O(n)$ words (Derived: The preconditioners used have $O(n)$ non-zero entries) == Description == Maximum-weight-basis (MWB) preconditioners == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.343"
- 11:1511:15, 15 February 2023 diff hist +332 N Boman; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $\tilde{O}(mn^{({1}/{2})})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == https://epubs.siam.org/doi/10.1137/S0895479801390637" current
- 11:1511:15, 15 February 2023 diff hist +300 N Bern; Gilbert; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $O(n loglogn)$ == Space Complexity == () == Description == Support Graph Preconditioning == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://dl.acm.org/citation.cfm?id=1117896"
- 11:1511:15, 15 February 2023 diff hist +555 N Spielman, Teng (Inexact Laplacian Solver SDD Systems Solvers) Created page with "== Time Complexity == $O(m log^c n)$ == Space Complexity == $O(n)$ words (Derived: Uses spanning trees and sparse Cholesky factorization which both take $O(n)$ space) == Description == Spectral Sparsification == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://dl.acm.org/doi/pdf/10.1145/1007352.1007372?casa_token=k60CrC_UJp0AA..."