Live data from Hacker News

Introduction to the Conjugate Gradient Method Without Agonizing Pain (1994) [pdf]

cs.cmu.edu

11–16 of 16 posts

Re: Introduction to the Conjugate Gradient Method Without Agonizing Pain (1994) [pdf]

#11
post #9

Important to note that this method only works on Hermitian (usually AKA symmetric) and positive-definite matrices, both of which are often pretty big qualifiers.

Did positive definite not imply Hermitian? I feel like I'm forgetting my linear algebra. Edit: Yup, Wikipedia agrees "this condition implies that M is Hermitian"; see their counterexample with a complex vector: https://en.wikipedia.org/wiki/Definite_matrix#Consistency_be... Note: Crucially, this is specific to the field of complex numbers (hence the discussion of Hermitian vs. just symmetry). For the field of real nu…

kind of. you can decompose an arbitrary matrix into symmetric and antisymmetric components: R = S + A. Since A = -A^H (anti-symmetric), for any vector x, = - => = 0. So for any matrix where > 0, you can add an arbitrary anti-symmetric matrix and keep the same induced quadratic form. So people typically enforce symmetry in their definitions because it is the only part that contributes to the quadratic form and is "nicer" to work with (always diagonalizable, positive eigenvalues, etc.)

This should generalize easily to the complex/Hermitian case.

Re: Introduction to the Conjugate Gradient Method Without Agonizing Pain (1994) [pdf]

#12

Earlier quoted context omitted.

Did positive definite not imply Hermitian? I feel like I'm forgetting my linear algebra. Edit: Yup, Wikipedia agrees "this condition implies that M is Hermitian"; see their counterexample with a complex vector: https://en.wikipedia.org/wiki/Definite_matrix#Consistency_be... Note: Crucially, this is specific to the field of complex numbers (hence the discussion of Hermitian vs. just symmetry). For the field of real nu…

kind of. you can decompose an arbitrary matrix into symmetric and antisymmetric components: R = S + A. Since A = -A^H (anti-symmetric), for any vector x, = - => = 0. So for any matrix where > 0, you can add an arbitrary anti-symmetric matrix and keep the same induced quadratic form. So people typically enforce symmetry in their definitions because it is the only part that contributes to the quadratic form and is "nic…

Thanks! But I think you might've missed a subtlety here:

> This should generalize easily to the complex/Hermitian case.

This doesn't seem to be true, in that it's actually impossible to have a non-Hermitian matrix C such that x†Cx > 0 over the complex numbers for all x. Whereas over the real numbers, with a matrix R, you can have x'Rx > 0 such that R is asymmetric.

The subtlety here is that x itself can be complex in the complex case, which further constraints C to be Hermitian - see the Wikipedia link I posted above.

In other words, "complex definiteness" is actually a stronger condition than "real definiteness", even for matrices without an imaginary part.

Re: Introduction to the Conjugate Gradient Method Without Agonizing Pain (1994) [pdf]

#13

Shewchuk’s work on mesh generation is nothing short of a masterpiece. I will always direct people to the source of his Triangle code as an example of what good, literate C code should look like. His Berkeley page is here: https://people.eecs.berkeley.edu/~jrs/

Warmly remember taking his computational geometry in undergrad. It was the most engaging and mathematically creative class I took in college.

Re: Introduction to the Conjugate Gradient Method Without Agonizing Pain (1994) [pdf]

#14

Earlier quoted context omitted.

kind of. you can decompose an arbitrary matrix into symmetric and antisymmetric components: R = S + A. Since A = -A^H (anti-symmetric), for any vector x, = - => = 0. So for any matrix where > 0, you can add an arbitrary anti-symmetric matrix and keep the same induced quadratic form. So people typically enforce symmetry in their definitions because it is the only part that contributes to the quadratic form and is "nic…

Thanks! But I think you might've missed a subtlety here: > This should generalize easily to the complex/Hermitian case. This doesn't seem to be true, in that it's actually impossible to have a non-Hermitian matrix C such that x†Cx > 0 over the complex numbers for all x. Whereas over the real numbers, with a matrix R, you can have x'Rx > 0 such that R is asymmetric. The subtlety here is that x itself can be complex in…

I spent ages looking for a proof of the complex cases during my PhD. Most proofs of CG begin "assuming a real, positive definite matrix".

Re: Introduction to the Conjugate Gradient Method Without Agonizing Pain (1994) [pdf]

#15

Earlier quoted context omitted.

Thanks! But I think you might've missed a subtlety here: > This should generalize easily to the complex/Hermitian case. This doesn't seem to be true, in that it's actually impossible to have a non-Hermitian matrix C such that x†Cx > 0 over the complex numbers for all x. Whereas over the real numbers, with a matrix R, you can have x'Rx > 0 such that R is asymmetric. The subtlety here is that x itself can be complex in…

I spent ages looking for a proof of the complex cases during my PhD. Most proofs of CG begin "assuming a real, positive definite matrix".

Yeah, the complex case seems to get ignored in many areas. I'm guessing it's not particularly useful for many applications.

Re: Introduction to the Conjugate Gradient Method Without Agonizing Pain (1994) [pdf]

#16

Earlier quoted context omitted.

kind of. you can decompose an arbitrary matrix into symmetric and antisymmetric components: R = S + A. Since A = -A^H (anti-symmetric), for any vector x, = - => = 0. So for any matrix where > 0, you can add an arbitrary anti-symmetric matrix and keep the same induced quadratic form. So people typically enforce symmetry in their definitions because it is the only part that contributes to the quadratic form and is "nic…

Thanks! But I think you might've missed a subtlety here: > This should generalize easily to the complex/Hermitian case. This doesn't seem to be true, in that it's actually impossible to have a non-Hermitian matrix C such that x†Cx > 0 over the complex numbers for all x. Whereas over the real numbers, with a matrix R, you can have x'Rx > 0 such that R is asymmetric. The subtlety here is that x itself can be complex in…

>it's actually impossible to have a non-Hermitian matrix C such that x†Cx > 0

Nice catch, it's been a few years since I had to think about these details.

Post reply on HN