User david ketcheson - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T07:54:06Z http://mathoverflow.net/feeds/user/20507 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109429/global-error-analysis-of-eulers-method/109454#109454 Answer by David Ketcheson for Global Error Analysis of Euler's Method David Ketcheson 2012-10-12T11:54:43Z 2012-10-12T11:54:43Z <p>Any analysis of global error must include information about how local errors are amplified in subsequent steps. So your statement </p> <blockquote> <p>I know that the local error at each step of Euler's method is O(t^2), where t is the time step. And since there are (b-a)/t steps, the order of the global error is O(t).</p> </blockquote> <p>isn't accurate without some assumption of stable error propagation.</p> <p>You are correct that the "derivation of the global error" given does not say anything about global error.</p> http://mathoverflow.net/questions/108646/is-is-preferable-to-use-a-difference-formula-of-higher-order-of-accuracy-for-spat/109314#109314 Answer by David Ketcheson for Is is preferable to use a difference formula of higher order of accuracy for spatial derivatives to solve this IVP problem ? David Ketcheson 2012-10-10T18:17:11Z 2012-10-10T18:17:11Z <p>You could use the method of lines to solve this PDE. If you use an explicit finite difference method, you will need to take a rather small time step (${\mathcal O(\Delta x^3))}$ due to the $u_{xxx}$ term.</p> <p>Given that you don't specify any boundary conditions, I will assume that you are solving the Cauchy problem. In that case (or in case of periodic boundary conditions), there is a <strong>much</strong> more efficient approach. Since your PDE is linear and the coefficients don't vary in space, you can solve in terms of Fourier modes. Decompose the initial data as usual:</p> <p>$$u(x,0) = \sum_k c_k\exp{ikx}.$$</p> <p>Then use the <em>ansatz</em></p> <p>$$u(x,0) = \sum_k g_k(t)\exp{ikx}$$</p> <p>with $g_k(0) = c_k$. Substituting this in your PDE gives</p> <p>$$g_k'(t) = ik a(t) - ik^3b + c.$$</p> <p>This can be solved very easily by numerical quadrature (or exactly, if $a(t)$ can be integrated symbolically).</p> http://mathoverflow.net/questions/102413/must-read-papers-in-numerical-analysis/102431#102431 Answer by David Ketcheson for "Must read" papers in numerical analysis David Ketcheson 2012-07-17T08:23:02Z 2012-07-17T08:23:02Z <p>S.K. Godunov, <em>A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics</em>, Matematicheskii Sbornik (1959). (in Russian)</p> <p>Virtually all modern methods for nonlinear hyperbolic PDEs are based on this.</p> http://mathoverflow.net/questions/100928/differentiability-of-minimax-objective-function-with-respect-to-a-decision-variab Differentiability of minimax objective function with respect to a decision variable David Ketcheson 2012-06-29T13:02:37Z 2012-07-16T15:22:01Z <p>I have the following optimization problem:</p> <p>$$\text{find } x= \min_{a} \max_{\lambda\in\Lambda} |R(h\lambda)|$$</p> <p>where $\Lambda$ is some finite, fixed set of complex numbers and $R(z)$ is a polynomial of degree at most $s$ of the form</p> <p>$$R(z) = 1 + z + \sum_{j=2}^{s}a_j z^j$$</p> <p>where $h>0$ is fixed and the real coefficients $a_j$ are the decision variables. Can it be shown that $x$ is a differentiable function of $h$? Are there general tools that might be useful for proving this type of property?</p> http://mathoverflow.net/questions/101522/sum-of-maxima-vs-the-maximum-of-the-sum/101932#101932 Answer by David Ketcheson for sum of maxima vs the maximum of the sum David Ketcheson 2012-07-11T09:44:17Z 2012-07-13T20:42:21Z <p>In some cases there exists no ordering of $\Gamma$ such that solving the problems in $\Gamma$ sequentially gives the optimal value of the original problem. </p> <p>Here is a simple counterexample. Let $i,j$ range from 1 to 2 and set $c_j=1, f(i,j)=1$ for all $i,j$. Take $U_{i,j}=1$ for $i=j$ and $U_{i,j}=2$ for $i\ne j$. Then the original problem is solved by taking $x_{1,1}=x_{2,2}=0$ and $x_{1,2}=x_{2,1}=1$, giving an objective function value of 4. But solving $\Gamma$ in either order leads to an objective function value of 3.</p> <p>Let's go through it step by step.</p> <p>The problem is $$\max x_{11} + x_{22} + 2x_{12} + 2x_{21}$$ subject to $$x_{11}+x_{21}\le 1$$ $$x_{12}+x_{22}\le 1$$</p> <p>For the other two problems, we have</p> <p>$$\max x_{11} + 2x_{12}$$ subject to $$x_{11}+x_{21}\le 1$$ $$x_{12}+x_{22}\le 1$$ which leads to <strong>$x_{12}=1$ AND $x_{11}=1$</strong>, in order to achieve a maximum value of 3. Notice that <strong>the solution to this problem in the comment below is not correct</strong>.</p> <p>Then the second problem becomes $$\max 2x_{21} + x_{22}$$ subject to $$x_{21}\le 0$$ $$x_{22}\le 0.$$</p> http://mathoverflow.net/questions/41994/basic-software-libraries-for-numerical-analysis-using-modern-programming-language/101334#101334 Answer by David Ketcheson for Basic software libraries for numerical analysis using modern programming languages? David Ketcheson 2012-07-04T18:43:37Z 2012-07-04T18:43:37Z <p>There are several good answers already, but none of them so far deal with <strong>high performance computing</strong>, which nowadays means computing on tens or hundreds of thousands of cores. I am aware of only three Python codes that have scaled to this level:</p> <ul> <li><a href="http://numerics.kaust.edu.sa/pyclaw/" rel="nofollow">PyClaw</a> (my code -- you can read about it and my take on HPC software development in Python in <a href="http://arxiv.org/abs/1111.6583" rel="nofollow">this paper</a>)</li> <li><a href="https://wiki.fysik.dtu.dk/gpaw/" rel="nofollow">GPAW</a></li> <li><a href="http://www.ctcms.nist.gov/fipy/" rel="nofollow">FiPy</a></li> </ul> <p>Of course, you can't write a performant numerical code entirely in Python, so typically these use a compiled language for performance-critical parts (in PyClaw, we use both Fortran and C). One reason for choosing Python is that automated tools like f2py and Cython make it easy to incorporate compiled code.</p> <p>I do not believe there are any high performance computing codes written in the languages you mention. I suspect modern supercomputers don't support those languages.</p> http://mathoverflow.net/questions/101293/what-method-can-i-employ-to-solve-this-optimization-problem-which-involves-min/101295#101295 Answer by David Ketcheson for what method can I employ to solve this optimization problem which involves \min? David Ketcheson 2012-07-04T09:06:39Z 2012-07-04T17:43:13Z <p>A common transformation when faced with a problem of this type:</p> <p>$${\rm maximize} \min (f(x), g(x))$$</p> <p>is to instead solve the equivalent problem</p> <p>$${\rm maximize} \ \ \ z$$ subject to $$z\le f(x); z\le g(x).$$</p> <p>This can be helpful, for instance, in making the problem more tractable for some numerical optimization methods (if they are better at handling inequality constraints rather than complicated objective).</p> <p>Many other transformations are possible; for instance, you can replace the inequality constraints above with equality constraints via <em>slack variables</em>. For a discussion of transformations of optimization problems, I recommend Section 4.1.3 of Boyd and Vandenberghe (<a href="http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf" rel="nofollow">free PDF here</a>). Actually, I recommend the whole book.</p> http://mathoverflow.net/questions/48724/convergence-of-finite-difference-method-for-boundary-value-ode/100406#100406 Answer by David Ketcheson for convergence of finite difference method for boundary value ODE David Ketcheson 2012-06-22T22:06:54Z 2012-06-22T22:06:54Z <p>A very straightforward explanation is given in <a href="http://faculty.washington.edu/rjl/fdmbook/" rel="nofollow">R.J. LeVeque's text</a>. In Chapter 2 there are simple explanations of how to show convergence for the linear problem in both the maximum norm and the Euclidean norm. There is also a discussion of the nonlinear problem. Numerical solution of nonlinear BVPs typically requires a nonlinear iterative solver, such as Newton's method, and the numerical discretization inherits the properties of Newton's method (i.e., it is only guaranteed to converge if you start sufficiently close to a solution, and the solution it converges to depends on the initial guess.</p> <p>The nonlinear example considered in the text is $y''(x)=\sin(x)$, and it is demonstrated that the numerical solution is non-unique (as is the analytic solution).</p> http://mathoverflow.net/questions/80059/numerically-track-spectrum-curves-of-a-parameter-dependent-linear-operator/85558#85558 Answer by David Ketcheson for numerically track spectrum curves of a parameter dependent linear operator David Ketcheson 2012-01-13T06:43:09Z 2012-01-13T06:43:09Z <p>I faced this problem a few years ago. In that case, I obtained a satisfactory approach along the lines of one of your suggestions. Specifically, I found that the eigenvectors changed relatively slowly with $t$. So I could associate the corresponding eigenvalue curves after an intersection with the right ones before an intersection by considering the similarity of the corresponding eigenvectors. I found that the inner-product $X^T_i Y_j$, where $X_i$ is one of the eigenvectors after the intersection and $Y_j$ is one of the eigenvectors after the intersection was a good measure of their similarity.</p> <p>By the way, you might get more answers by posting this on <a href="http://scicomp.stackexchange.com/" rel="nofollow">http://scicomp.stackexchange.com/</a></p> http://mathoverflow.net/questions/4329/roots-of-truncations-of-ex-1 Comment by David Ketcheson David Ketcheson 2013-05-07T15:25:54Z 2013-05-07T15:25:54Z The links are dead. http://mathoverflow.net/questions/115495/matrix-minimax-problem Comment by David Ketcheson David Ketcheson 2012-12-06T08:35:56Z 2012-12-06T08:35:56Z What does &quot;*&quot; mean here? If just multiplication, it would be clearer to omit the symbol. http://mathoverflow.net/questions/112261/how-to-prove-this-problem-that-involves-ceiling-function Comment by David Ketcheson David Ketcheson 2012-11-14T16:57:58Z 2012-11-14T16:57:58Z This is neither numerical analysis nor functional analysis (unless there is some application I'm missing). http://mathoverflow.net/questions/112382/special-spharse-matrices Comment by David Ketcheson David Ketcheson 2012-11-14T16:56:26Z 2012-11-14T16:56:26Z You might ask on scicomp.stackexchange.com. http://mathoverflow.net/questions/111633/upper-bound-on-largest-eigenvalue-of-a-real-symmetric-nn-matrix-with-all-main-di Comment by David Ketcheson David Ketcheson 2012-11-09T12:10:30Z 2012-11-09T12:10:30Z In the literature, such matrices (without the sparseness requirement) are referred to as $L$-matrices. If they are diagonally dominant, they are referred to as $M$-matrices. Many things are known about such matrices, so those keywords may help. http://mathoverflow.net/questions/109506/solving-system-of-nonlinear-equations Comment by David Ketcheson David Ketcheson 2012-10-22T04:02:14Z 2012-10-22T04:02:14Z You might try asking on scicomp.stackexchange.com. http://mathoverflow.net/questions/109506/solving-system-of-nonlinear-equations/109540#109540 Comment by David Ketcheson David Ketcheson 2012-10-22T04:00:08Z 2012-10-22T04:00:08Z This certainly won't give <i>all</i> solutions. http://mathoverflow.net/questions/109506/solving-system-of-nonlinear-equations Comment by David Ketcheson David Ketcheson 2012-10-18T10:28:17Z 2012-10-18T10:28:17Z @Pat M: sorry, I missed the &quot;all solutions&quot; part. For general nonlinear functions, I believe there is no such algorithm. http://mathoverflow.net/questions/109429/global-error-analysis-of-eulers-method Comment by David Ketcheson David Ketcheson 2012-10-12T11:55:13Z 2012-10-12T11:55:13Z This question would be more appropriate on Math.SE, as it pertains to undergraduate numerical analysis. http://mathoverflow.net/questions/107777/is-there-a-krylov-subspace-method-for-solving-depsilons-where-d-is-diagonal-ep Comment by David Ketcheson David Ketcheson 2012-10-10T18:19:55Z 2012-10-10T18:19:55Z I recommend asking this question on scicomp.stackexchange.com. http://mathoverflow.net/questions/107068/numerical-methods-for-discontinuous-odes Comment by David Ketcheson David Ketcheson 2012-09-13T10:15:22Z 2012-09-13T10:15:22Z You may want to ask this question at scicomp.stackexchange.com. http://mathoverflow.net/questions/101522/sum-of-maxima-vs-the-maximum-of-the-sum/101932#101932 Comment by David Ketcheson David Ketcheson 2012-07-14T07:16:40Z 2012-07-14T07:16:40Z @john, Your solution of this problem (in comments) is not correct. I have made it completely explicit for you now. http://mathoverflow.net/questions/102017/fast-inversion-of-a-special-kind-of-matrices-approximations-are-ok Comment by David Ketcheson David Ketcheson 2012-07-12T10:16:00Z 2012-07-12T10:16:00Z I suggest asking on <a href="http://scicomp.stackexchange.com" rel="nofollow">scicomp.stackexchange.com</a>. http://mathoverflow.net/questions/102023/large-scale-sparse-system-of-linear-equations Comment by David Ketcheson David Ketcheson 2012-07-12T10:14:35Z 2012-07-12T10:14:35Z I suggest asking on scicomp.stackexchange.com. But you'll want to clarify the question. http://mathoverflow.net/questions/41994/basic-software-libraries-for-numerical-analysis-using-modern-programming-language Comment by David Ketcheson David Ketcheson 2012-07-04T18:32:51Z 2012-07-04T18:32:51Z Supercomputers don't have Java compilers. Of course, one may argue about whether this is a cause or an effect.