Question: I was trying to run test cases for CG and I need to generate:

* symmetric positive definite matrices
* of size > 10,000
* **FULL DENSE**
* Using only matrix indices and if necessary 1 vector
(Like $A(i,j) = \dfrac{x(i) - x(j)}{(i+j)}$)
* With condition number less than 1000.

I have tried:

1. Generating random matrices using `A=rand(N,N)` and then `A'A` to make it Sym. PD. [This increases condition number]
2. Using the vector appraoch as shown but I can't seem to get a function of `(x,i,j)` which will ensure Sym and PD.

After much experimentation, I came up with:

`a(it,jt) = (vec(it)+vec(jt))/((it-1)^2+(jt-1)^2);` If $it \neq jt$

`a(it,it) = x(it)` if $it=jt$

But this is PD till about 500x500.

1. [XLATMR](http://math.nist.gov/MatrixMarket/data/misc/xlatmr/xlatmr.html). [With all the grading and scaling, its too difficult to understand. Especially since I cannot understand the underlying linear algebra]

Can someone give me a function in x (vector) and i,j (indices) which meets the above requirements?

Answer: 
To get a dense positive definite matrix with condition number $c$ cheaply, pick a diagonal matrix $D$ whose diagonal consists of numbers from $[1,c]$ (which will be the eigenvalues), with $1$ and $c$ chosen at least once, and a vector $u$. Then apply a similarity transformation, via Householder transformations, to form the matrix $A:=(I-tuu^T)D(I-tuu^T)$, where $t=2/u^Tu$. 

To form this matrix with $O(n^2)$ operations, compute $v:=Du$, $s:=t^2u^Tv/2$, $w:=tv-su$ in $O(n)$ operations and then $A$ as $A=D-uw^T-wu^T$. (If you choose $u$ as the all-one vector, the number of multiplications needed is only $O(n)$.)

Note that the behavior of CG depends a lot on the eigenvalue distribution, which you can easily confirm by varying $D$.

(Adding $\alpha$ to an arbitrary symmetric matrix $A$ needs $\alpha$ larger than the largest eigenvalue. This is hard to compute; so one would have to choose $\alpha=\|A\|$, but then the condition number will generally be very small, not a realistic test case for CG.)
Try adding a large number $\alpha$ (on the order of the norm of the matrix) to the diagonal entries of your matrix. This is equivalent to adding $\alpha$ to each of your eigenvalues and should improve the condition number by reducing the gap between the largest and smallest eigenvalues.