Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

• p. 19 Lemma 6.1 statement

  is at least min(8w/n2, w/n), where w is the least weight of an edge of G and n is the dimension

• p. 19 Proof of Lemma 6.1, last sentence

  So, the smallest eigenvalue of the matrix induced on S1 is at least

Only the authors can say what is right here.

Judge's note: I reworked the step. The smallest eigenvalue of L1 + D1 is not bounded below by min(λ2(L1), 1^T D1 1/|S1|), because x^T D1 x mixes the constant direction with the directions orthogonal to it. Counterexample, checked against the stated hypotheses: G is the unit-weight path 0–1–2 and A is the principal sub-matrix on {1,2}, so A = [[2,-1],[-1,1]], w = 1 and n = dim(A) = 2. A has trace 3 and determinant 1, so its eigenvalues are (3±√5)/2. A is positive definite and λmin ≈ 0.382 < min(8/4, 1/2) = 0.5. For larger cases, a path grounded at one end with dimension 10 has λmin = 4 sin^2(π/42) ≈ 0.0223 < 0.08. The lemma as printed therefore fails; a smaller constant would be needed.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 22 Proof of Lemma 6.4, bound on ‖x^{i+1}‖

  ≤ 5k ∥x i∥ + 2 ∥B−1b∥

• p. 23 Proof of Lemma 6.4

  ≤ 2k√n ∥x i∥∞

Only the authors can say what is right here.

Judge's note: I checked a counterexample against the stated hypotheses on p.22. A = [[1.25,-1],[-1,1.25]] is SDDM with norm 2.25 ≤ 3, and B = diag(0.001, 0.85). Then B^{-1}A = [[1250,-1000],[-1.1765,1.4706]], with trace 1251.47, determinant 661.76 and eigenvalues ≈ 0.529 and 1250.94. So λmin = 1/2 and λmax = 2k with k ≈ 625.47 are admissible, with β = 1000. But ‖B^{-1}A‖2 ≥ ‖row 1‖ ≈ 1600.8, so 1 + 2·1600.8 ≈ 3202.6 > 5k ≈ 3127.4, and ‖B^{-1}A‖∞ = 2250 > 2k√2 ≈ 1769. The proof states that it uses 2- and ∞-norm relations (p.22–23), so the step is false in the norms it uses. The (5k+1)^i growth bound feeding the lemma's stated bound is therefore not proved as printed.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 23 Proof of Lemma 6.4, 'Finally, we find'

  ≤ (1 + γ3) ∥ˆx i −x i∥∞ + (1 + γ3) ∥ˆz i −z i∥∞

• p. 22 Proof of Lemma 6.4

  Our conditions on λmin and λmax imply that τi ≤ 2 for all i.

Only the authors can say what is right here.

Judge's note: The recurrence is x^{i+1} = x^i − τ_i z^i + τ_i B^{-1}b (p.22), with τ_i = 1/(cos θ_i (λmax−λmin)/2 + (λmax+λmin)/2) (algorithm, text line 667). τ_i can approach 1/λmin = 2 when λmin = 1/2. The ẑ−z and f(b)−B^{-1}b errors should therefore carry a factor τ_i. With τ_i near 2 the coefficient of ‖x̂^i−x^i‖ becomes about (1+γ3)(1+28β), not (1+γ3)(1+14β) ≤ 15β. The printed constants 15β and 17 in the lemma's bound are therefore not established by this proof.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 16 Proof of Lemma 5.3, display

  (by Proposition 4.1 (e))

• p. 10 Proposition 4.1

  (d) If B has 2(n −1 + j) nonzero off-diagonal entries

Judge's note: Page 10 shows that Proposition 4.1 lists (a) through (d) only. The step on p.16, B_i^{-1} = P^{-T}L^{-T}[I 0;0 A_i^{-1}]L^{-1}P^{-1}, follows from the factorization B = PLCL^TP^T displayed at the start of Section 4.1, not from any part of the proposition. The pointer leads nowhere.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 50 Reference [EEST08]

  SIAM Journal on Computing, 32(2):608–628, 2008.

• p. 50 reference [EEST08]

  SIAM Journal on Computing, 32(2):608–628, 2008

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: that 'Lower-stretch spanning trees' appeared in SIAM J. Comput. volume 38 (2008), and that volume 32 is from 2002–03. The page 50 image shows exactly '32(2):608–628, 2008'. The volume number needs checking by the authors.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 52 Reference [Sot10]

  Andrew Sothers. On the complexity of matrix multiplication. PhD thesis, University of Edinburg, 2010.

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: that the thesis author is Andrew Stothers and that the university is spelled 'Edinburgh'. The page 52 image shows 'Sothers' and 'Edinburg' as quoted, so this is not an extraction artefact.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 2 Introduction, roadmap paragraph

  in positive definite SDD0 matrices with nonnegative off-diagonal entries

• p. 8 Section 3.2

  to the problem of solving a system of equations in an irreducible SDDM-matrix

• p. 2 Intro, paragraph on Section 3

  positive definite SDD0 matrices with nonnegative off-diagonal entries

• p. 9 Section 3.2

  we need only consider the problem of solving systems in SDDM-matrices

Judge's note: Page 2 image shows 'nonnegative off-diagonal entries'. Section 1.1 (p3) defines SDDM0 as SDD0 matrices with non-positive off-diagonal entries and SDDM as the positive definite ones. Section 3.2 (p9) says Gremban's reduction gives 'a system that is twice as large in a SDDM-matrix'. So the sign condition in the roadmap is reversed; the fix is 'non-positive'.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 8 Proposition 3.6 and preceding sentence

  A singular irreducible SDDM-matrix is a Laplacian matrix

• p. 3 Section 1.1 definitions

  We let SDDM be the class of positive-definite SDDM0 matrices.

Judge's note: p3 image: 'We let SDDM be the class of positive-definite SDDM0 matrices.' p8 image: Proposition 3.6 and the preceding sentence refer to singular SDDM-matrices, which by definition cannot exist. Read as written, the proposition is vacuous; the intended class is SDDM0.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 20 Proof of Lemma 6.3, first display

  ℓ ≤ logk/3h 2m/(66h + 5) ≤ logk/3h m.

Only the authors can say what is right here.

Judge's note: On p.13 the Repeat loop runs at least once and stops at the first i with dim(A_i) < 66h+6. So dim(A_{ℓ−1}) ≥ 66h+6, noff(A_{ℓ−1}) ≥ 66h+5 and noff(A_{ℓ−1}) ≤ (3h/k)^{ℓ−1} m. This gives ℓ ≤ 1 + log_{k/3h}(m/(66h+5)). The printed bound substitutes a factor 2 for a factor k/3h ≈ 65h. Counterexample: when 2m < 66h+5 (for example a tree with n = 100 and h ≈ 6.6), the printed right-hand side is negative, yet ℓ ≥ 1. With n = 1000, m = 999 and h = 10, it is about 0.17. Part (a) still follows from the corrected bound, because k ≤ (66h+5)^2 and k/3h ≥ k^{1/2} give k^ℓ ≤ m^2. The stated result stands; the step does not.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 22 Proof of Lemma 6.3, bound on ‖L^{-1}‖∞

  ≤ n · n2e−3/200/

• p. 21 Proof of Lemma 6.3

  e−3/100λmin(A)/n4

• p. 21 Proof of Lemma 6.3

  its diagonals lie between 2e3/100 and e−3/100λmin(A)/n4

• p. 22 bound on ‖L^{-1}‖∞

  n · n2e−3/200/

Only the authors can say what is right here.

Judge's note: Pages 21–22: the entries of D1 are square roots of diagonals of B̂_i, which are at least e^{−3/100}λmin(A)/n^4. Inverting gives entries at most e^{3/200} n^2/√λmin(A) ≈ 1.015 n^2/√λmin. The printed e^{−3/200} is smaller and does not follow. The final bound 2n^3/√λmin(A) still holds because e^{0.015} < 2. The reversed order in "between 2e^{3/100} and e^{−3/100}λmin(A)/n^4" is only stylistic.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 23 Proof of Lemma 6.4, last line

  (1 + γ3)(1 + 14β) ≤ 15β,

• p. 22 Lemma 6.4 hypotheses

  Let β ≥ 1 be a number

Only the authors can say what is right here.

Judge's note: The inequality is equivalent to 1 + γ3(1+14β) ≤ β. It fails at β = 1 for any γ3 > 0 (γ3 = 3u/(1−3u) > 0). The hypotheses on p.22 permit β = 1, since only ‖B^{-1}‖∞ ≤ β is required, and p.23 notes ‖B^{-1}‖∞ ≥ 1/6√n. The step is false at the boundary. The effect is a constant-level slip of order γ3.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 24 Proof of Lemma 6.4, top display

  (as γ3β + θ ≤2β)

Only the authors can say what is right here.

Judge's note: Page 24. The last inequality needs 2βb0 ≤ θ√n(5k+1)^{i−1}βb0, i.e. θ√n(5k+1)^{i−1} ≥ 2. At i = 1 and θ ≤ 1/(10n), this means √n·θ ≤ 1/(10√n) < 2, so the step fails as printed. The likely intent is γ3β + θ ≤ 2θ, which holds since θ ≥ 12knβγn ≥ γ3β. That gives a θ-proportional term and leaves the lemma's form intact up to constants.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 24 Proof of Lemma 6.5

  ≤7n4γn ∥ß∥∞/

• p. 25 Proof of Lemma 6.5, top

  ≤12n7γn ∥b∥∞/λmin(A).

• p. 25 Proof of Lemma 6.5, top of page

  ≤12n7γn ∥b∥∞/λmin(A)

Only the authors can say what is right here.

Judge's note: Pages 24–25: the only inequalities cited are the factor 7n^4 and the factor 2n^3, whose product is 14n^7. The printed 12n^7 is smaller and does not follow. The constant is absorbed into d1, so Lemma 6.5's stated form survives.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 26 Proof of Theorem 6.6

  γn ≤θℓλ2 max(A)/50n8.

• p. 24 Lemma 6.5 hypothesis

  γn ≤θλ2 min(A)/50n8

• p. 26 Proof of Theorem 6.6

  γn ≤θℓλ2 max(A)/50n8

• p. 24 Lemma 6.5 hypothesis

  γn ≤ θλ2

Only the authors can say what is right here.

Judge's note: The p. 24 image shows λ²_min in the Lemma 6.5 hypothesis. The p. 26 image shows λ²_max in the proof of Theorem 6.6, just after 'We need to establish that there exist numbers θi that satisfy the conditions of Lemma 6.5'. Since λmax ≥ λmin, the printed condition is weaker than the hypothesis it is meant to satisfy. With λmin in its place, the stated bit bound O(log(κ/ε)log^{d3} n) is unaffected, so the theorem stands. The faulty step is the substituted subscript.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 25 Proof of Lemma 6.5

  α = 17(15β + 5k + 1)tθ√nβ,

• p. 25 Proof of Lemma 6.5

  ∥ˆy −y∥∞ ≤ αθ

Only the authors can say what is right here.

Judge's note: Lemma 6.4 (p. 23; proof end on p. 24) gives ‖x̂^t − x^t‖ ≤ 17√n(15β+5k+1)^t βθ‖b‖∞. With α defined on p. 25 to include θ, that bound is α‖ŝ1‖, not αθ‖ŝ1‖. The printed bound is smaller by a factor θ and does not follow from Lemma 6.4. Later steps ('α ≤ d1(nκ)^{d2√k}', '≤ 2αθ‖ŝ‖', and the final θd1(...) bound) are consistent only if θ is dropped from α. So the definition of α is a slip, and the lemma as stated still stands.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 56 Proof of Lemma C.1

  the only way sets Wj and Wk with j < k can overlap is if the set Wj was formed at step 3.c.ii

• p. 55 decompose/sub pseudo-code, steps 7(b) and 7(e)

  (e) Set Wh = {v}.

• p. 33 Figure 2 caption

  W5 is a singleton set and that it overlaps W4.

Only the authors can say what is right here.

Judge's note: Checked the pseudo-code on page 55. Step 7(b) sets Wh = Usub ∪ {v}; step 7(d) increments h; step 7(e) sets Wh = {v}. The two consecutive sets therefore both contain v. The Figure 2 caption (page 33) shows such a case: singleton W5 overlaps W4. The proof on pages 56–57 defines Xj = Wj − v only for sets formed at 3.c.ii and then states that X1,…,Xh are disjoint. That is false for the 7(b)/7(e) pair, where Xh = Wh and Xh+1 = {v} share v. The step looks repairable by also removing v from sets formed at 7(b). Edges (x,v) with x in Usub are in both Fsub and Fv, so they are assigned to both sets and give the edge (h,h+1). The lemma itself therefore probably stands, but the proof step is wrong as printed.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 43 Lemma 11.4, inequality (30)

  E ≼(3β + 126β max(1, log2 η(E))) · T + 120β · Es,

• p. 40 RootedUltraSparsify step 8

  For b ∈{1, . . . , ⌈log2 η(E)⌉}:

• p. 44 Proof of Lemma 11.4

  Inequality (30) in the statement of the lemma follows from these inequalities and F = P

• p. 40

  f ∈F : φ(f) ∈(2b−1, 2b]

Only the authors can say what is right here.

Judge's note: Chaining (32)–(35) on p. 43 gives F^b ≼ 2βT + (5/2)(16βT + 2F_s^b) ≼ 42βT + 40βE_s^b. Then (31) with F = Σ_b F^b (p. 44) gives a T coefficient of 3β + 126β·(number of classes). Step 8 on p. 40 creates ⌈log2 η(E)⌉ classes, and (29) uses the ceiling. For η(E) = 3 the classes [1,2] and (2,4] can both be nonempty, so 2 > log2 3. The discrepancy affects only constants (517 in UltraSparsify). The interval (2^{b−1}, 2^b] flagged in note 3 is a legitimate half-open interval, not a bracket error.

Second check: another model agreed, code check

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 48 Proof of Theorem 11.5, 'We conclude' display

  +120βr·Ar ≼516(η(E)/t) max(1, log2 η(Er))T r+120(η(E)/t)Ar

• p. 48 Proof of Theorem 11.5, 'We conclude'

  +120(η(E)/t)Ar

• p. 48 proof of Thm 11.5, 'We conclude' display and following lines

  516(η(E)/t) max(1, log2 η(Er))T r+120(η(E)/t)Ar

• p. 48 proof of Theorem 11.5, 'We conclude' line and the two following displays

  120βr · Ar ≼ 516(η(E)/t) max(1, log2 η(Er))T r+120(η(E)/t)Ar

Only the authors can say what is right here.

Judge's note: The p. 48 image shows the factor 4 applied to the tree term (129·4 = 516) but not to 120βr. The only bound stated is βr ≤ 4η(E)/t, so the A^r coefficient should be 480η(E)/t, and the 120 is carried into the next displays. Since η(E)/t = k/(517·max(1,log2 η(E))·⌈log2 n⌉), 480η(E)/t ≤ k still holds, so (39) stands.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send