3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Wolfgang Bangerth
    Commented Jul 26, 2013 at 22:51

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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. $$

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Wolfgang Bangerth
    Commented Jul 27, 2013 at 3:31
  • $\begingroup$ @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. $\endgroup$
    – Shuhao Cao
    Commented Jul 27, 2013 at 3:58
  • 1
    $\begingroup$ That's the definition of bad condition number :-) $\endgroup$
    – Wolfgang Bangerth
    Commented Jul 27, 2013 at 10:55
  • $\begingroup$ I would expect that all matrices with smoothly varying coefficients are ill conditioned. $\endgroup$
    – Guido Kanschat
    Commented Jul 27, 2013 at 16:57
  • 1
    $\begingroup$ 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). $\endgroup$
    – Jack Poulson
    Commented Jul 27, 2013 at 17:29
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.