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 Gentleman; Morven and Gordon Sande radix-4 algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [359 bytes] Admin (talk | contribs) (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 == 1966 == Reference == http://cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf")
- 11:15, 15 February 2023 Yavne Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [350 bytes] Admin (talk | contribs) (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 == 1968 == Reference == https://dl.acm.org/citation.cfm?id=1476610")
- 11:15, 15 February 2023 Bruun's FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes O(n) remainders per stage; storage space can be reused across stages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == https://ieeexplore.ieee.org/document/1163036/")
- 11:15, 15 February 2023 Rader–Brenner algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [352 bytes] Admin (talk | contribs) (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 == 1976 == Reference == https://ieeexplore.ieee.org/document/1162805")
- 11:15, 15 February 2023 Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [347 bytes] Admin (talk | contribs) (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 == -")
- 11:15, 15 February 2023 Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [409 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Fleury's algorithm + Thorup (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) [408 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Hierholzer's algorithm (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) [308 bytes] Admin (talk | contribs) (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 == -")
- 11:15, 15 February 2023 Fleury's algorithm + Tarjan (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) [401 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Mucha and Sankowski ( Maximum-Weight Matching) (hist | edit) [268 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Micali; Vazirani ( Maximum-Weight Matching) (hist | edit) [276 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Edmonds (Maximum-Weight Matching Maximum-Weight Matching) (hist | edit) [418 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Lipton; Mehta (2-player Nash Equilibria) (hist | edit) [368 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Hungarian algorithm (Bipartite Maximum-Weight Matching Maximum-Weight Matching) (hist | edit) [464 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Lemke–Howson algorithm (2-player Nash Equilibria) (hist | edit) [347 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 De Prisco (Approximate OBST Optimal Binary Search Trees) (hist | edit) [502 bytes] Admin (talk | contribs) (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...")
- 11:15, 15 February 2023 Levcopoulos; Lingas; Sack (Approximate OBST Optimal Binary Search Trees) (hist | edit) [402 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Yao (OBST Optimal Binary Search Trees) (hist | edit) [310 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Naive algorithm (OBST Optimal Binary Search Trees) (hist | edit) [412 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Knuth's DP algorithm (OBST Optimal Binary Search Trees) (hist | edit) [362 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Modified Knuth's DP algorithm (OBST Optimal Binary Search Trees) (hist | edit) [362 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Hu–Tucker algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) (hist | edit) [331 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Garsia–Wachs algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) (hist | edit) [371 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Heap's algorithm (All Permutations All Permutations) (hist | edit) [347 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Tompkins–Paige algorithm (All Permutations All Permutations) (hist | edit) [360 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Steinhaus–Johnson–Trotter algorithm (All Permutations All Permutations) (hist | edit) [420 bytes] Admin (talk | contribs) (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:15, 15 February 2023 SMAWK algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix) (hist | edit) [416 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Naive algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix) (hist | edit) [378 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Faugère F5 algorithm (Gröbner Bases Gröbner Bases) (hist | edit) [482 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Faugère F4 algorithm (Gröbner Bases Gröbner Bases) (hist | edit) [500 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Buchberger's algorithm (Gröbner Bases Gröbner Bases) (hist | edit) [401 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Dual subgradients and the drift-plus-penalty method (Stochastic optimization Convex Optimization (Non-linear)) (hist | edit) [324 bytes] Admin (talk | contribs) (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 ==")
- 11:15, 15 February 2023 Subgradient method (General, Constrained optimization Convex Optimization (Non-linear)) (hist | edit) [376 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Ellipsoid method (General, Constrained optimization Convex Optimization (Non-linear)) (hist | edit) [383 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Wolfe; Lemaréchal; Kiwiel (General, Constrained optimization Convex Optimization (Non-linear)) (hist | edit) [413 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Gomory's cutting method (ILP;MILPs Convex Optimization (Non-linear)) (hist | edit) [431 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Sattolo's algorithm (Cyclic Permutations Generating Random Permutations) (hist | edit) [321 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Durstenfeld's Algorithm 235 (General Permutations Generating Random Permutations) (hist | edit) [295 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Fisher–Yates/Knuth shuffle (General Permutations Generating Random Permutations) (hist | edit) [411 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Gosper's algorithm ( Cycle Detection) (hist | edit) [408 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Brent's algorithm ( Cycle Detection) (hist | edit) [336 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Floyd's tortoise and hare algorithm ( Cycle Detection) (hist | edit) [338 bytes] Admin (talk | contribs) (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")
- 11:15, 15 February 2023 Naive Implementation (Exact Laplacian Solver SDD Systems Solvers) (hist | edit) [473 bytes] Admin (talk | contribs) (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 == -")
- 11:15, 15 February 2023 Daitch; Spielman (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [498 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Lee; Peng; Spielman (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [513 bytes] Admin (talk | contribs) (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...")
- 11:15, 15 February 2023 Kelner; Orecchia; Sidford; Zhu (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [431 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Briggs; Henson; McCormick ( SDD Systems Solvers) (hist | edit) [321 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Blelloch; Koutis; Miller; Tangwongsan (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [434 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Koutis; Miller and Peng (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [444 bytes] Admin (talk | contribs) (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:15, 15 February 2023 Boman; Chen; Hendrickson; Toledo (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [452 bytes] Admin (talk | contribs) (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")