# Smoothly varying dense matrices arising from computational science

I have written an algorithm to solve a dense system with smoothly varying entries. This means I assume there is no large jump from any entry to its neighbors.

I would love to use real-application-generated matrix to test my algorithm, but I cannot think of any that satisfies my assumption out of my stupid head. Any suggestions?

• Can you explain in more (mathematical) detail what you mean by "smoothly varying entries"? One typically uses this expression if an object (e.g., a matrix entry) depends on some parameter. – Wolfgang Bangerth Jul 26 '13 at 22:51

A differential operator will always result in rows with sum zero. Furthermore, if you want to preserve the locality of the differential operator, the entries with opposite signs will be neighbors (possibly separated by zeros).

Smoothly varying entries come up if you discretize an integral operator with smooth kernel by a collocation or quadrature method. I recommend you look into applications there.

How about a problem of $L^2$-projection on to the polynomial space spanned by $$\{1,1+\epsilon x, 1+\epsilon x^2, \dots, 1+\epsilon x^n\},$$ for $\epsilon \ll 1$, $x\in [0,1]$. Then the matrix has entry $$A_{ij} = \int^1_{0} (1+\epsilon x^i)(1+\epsilon x^j) dx = 1 + \frac{\epsilon}{i+1}+\frac{\epsilon}{j+1} + \frac{\epsilon^2}{i+j+1},$$ with right hand side $B$ is $$b_j = \int^1_0 (1+\epsilon x^j) f(x) dx.$$ Then the projection of $f$ has coefficients $F = (f_1,\dots,f_n)$ can be solved by $$A F = B.$$

• This is the Hilbert matrix, which is known to have a terrible condition number. You can't do a projection onto monomials if you want to have more than the first 4 or 5 terms -- you need to orthogonalize the polynomials first. – Wolfgang Bangerth Jul 27 '13 at 3:31
• @WolfgangBangerth I just tried to cook up some example OP asked...the variation of different entries are small. Sure it has bad condition number because essentially different rows are almost linearly dependent. – Shuhao Cao Jul 27 '13 at 3:58
• That's the definition of bad condition number :-) – Wolfgang Bangerth Jul 27 '13 at 10:55
• I would expect that all matrices with smoothly varying coefficients are ill conditioned. – Guido Kanschat Jul 27 '13 at 16:57
• Depending upon your requirement on smoothness, the class of discrete Fourier transforms might be a good counter-example, as their condition number is one (they are unitary if properly scaled). – Jack Poulson Jul 27 '13 at 17:29

A method of moments solution to the Helmholtz equation will have smoothly varying coefficients as a function of frequency (we usually want to compute frequency spectra, so this is very common). Also, planewave expansions are dense, and should also vary continuously with respect to frequency. I wrote a package called S4, which is almost always used to compute spectra, and it requires many linear solves and eigenvalue problems of smoothly varying dense matrices.