most recent 30 from http://mathoverflow.net 2013-05-21T09:12:31Z http://mathoverflow.net/feeds/question/50822 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50822/reasonable-random-matrices-to-test-numerical-algorithms Martin 2010-12-31T18:37:48Z 2011-02-10T15:51:20Z

<p>Hello,</p> <p>in numerical analysis, it is common to compare the behavior of different algorithms, and of different implementation of algorithms. This occurs not only on the theoretical level, but also on the concrete level of implementation - and not to forget, it serves the purpose of demonstration.</p> <p>A prominent problem is the solution of linear systems, both general as well as various subcases.</p> <p>To test, benchmark and profile numerical implementations, you run your work on several instances of the problem. However, it is difficult question to obtain a good set of these instances. You want to inspect pathological cases (diff. degrees of ill-conditionedness) as well as "real-life" examples (whatever this may mean). Ideally, you have an algorithm which puts out matrices with certain properties in a "reasonable" probability measure. A good notion of "reasonable" might be accessible, as most such LSE problems from physics or simulations have much more structure as is actually demanded by the algorithms in theory.</p> <p>In so far, I wonder whether there are works in numerical analysis how to, given $n \in \mathbb N$ randomly produce</p> <ul> <li>a sequence of ${n \times n}$-matrices</li> <li>optionally constraint to be symmetric, positive definite, well-conditioned</li> <li>which is reasonable in whatever sense</li> </ul> <p>This is probably an interesting topic within the theory of numerical algorithms.</p> <p>Thanks, Martin</p>

http://mathoverflow.net/questions/50822/reasonable-random-matrices-to-test-numerical-algorithms/50830#50830 Igor Rivin 2010-12-31T20:12:49Z 2010-12-31T20:12:49Z

<p>This is an impossible question to answer (so maybe this should be a comment...), since (for example) the sparsity patterns of the matrices encountered are completely different in statistical applications and in finite elements -- each problem class leads to a completely different distribution on the space of matrices. As a result, all the papers I have seen in numerical analysis are of the sort: we tried heuristic X and it worked well for problem Y. This gives us reasonable confidence that it will work for problem Z, such that $|Z-Y| &lt; \epsilon.$ People are very careful not to make general statements.</p> <p>DISCLAIMER: I am not a professional numerical analyst, nor do I play one on TV.</p>

http://mathoverflow.net/questions/50822/reasonable-random-matrices-to-test-numerical-algorithms/50871#50871 Federico Poloni 2011-01-01T18:02:44Z 2011-01-01T18:02:44Z

<p>A good set of benchmark matrices often depends on the problem being solved (sparse solvers, eigenvalue problems, special structures, et cetera). Good sets of benchmarks are hand-picked, and are publication-worthy in themselves (they get lots of citations).</p> <p>Among many of them, I shall mention here the all-purpose Matlab's <code>gallery</code>, based on Higham's books (and in particular tweaking the parameters in <code>randsvd</code> could suit your needs well), the University of Florida's sparse matrix collection , <code>carex</code> and <code>darex</code> by Benner for control problems, and several image sets for image reconstruction and compression algorithms, such as the baboon or the long-debated <a href="http://en.wikipedia.org/wiki/Lenna" rel="nofollow">Lenna</a>.</p>

http://mathoverflow.net/questions/50822/reasonable-random-matrices-to-test-numerical-algorithms/54906#54906 Diego de Estrada 2011-02-09T17:26:10Z 2011-02-10T15:51:20Z

<p>One way to generate random matrices while constraining it, is to generate its LU decomposition first. That way you can restrict it to be symmetric ($L=U^T$) and gives you the control over its spectrum.</p> <p>In [S.M. Rump. A Class of Arbitrarily Ill-conditioned Floating-Point Matrices. SIAM J. Matrix Anal. Appl. (SIMAX), 12(4):645-653, 1991] there is a related method for generating very ill-conditioned matrices.</p>

http://mathoverflow.net/questions/50822/reasonable-random-matrices-to-test-numerical-algorithms/54950#54950 Andrew D. King 2011-02-09T23:08:52Z 2011-02-09T23:08:52Z

<p>One way to get useful information on a numerical algorithm is to choose by hand a well-conditioned or even more an ill-conditioned example and perturb it randomly. In fact it is useful to perturb it randomly such that the perturbations form a sequence approaching zero; you can then look at the sequence of solutions that you get and see what you can say about error propagation and the like.</p>