Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

4
votes
2answers
503 views

Numerical solution to diffusion-like equation with negative diffusion coefficient region?

I am trying to numerically solve the initial value problem (see later discussion for ICs) $$ x \frac{\partial f}{\partial t} = \frac{\partial}{\partial x} (1-x^2) \frac{\partial f}{\partial x} - f$$ ...
1
vote
1answer
413 views

Is there a quick way to find all roots of a real polynomial with multiple variables?

If I am asked to find the roots of a polynomial of one variable, I will use a computer to estimate the eigenvalues of its companion matrix. Now suppose I'm given a real polynomial of multiple ...
4
votes
1answer
243 views

How to get an expression for this integral(Numerically/Analytically)

I have the following problem: I need to evaluate the integral $$\int_{\cos(\alpha)}^{1} P_l(t)P_{l'}(t) dt $$ for $\alpha \in [0,\pi]$ and each combination of $l$ and $l'$, where $P_l$ is the l-th ...
2
votes
0answers
27 views

In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
3
votes
1answer
331 views

Practical error-estimates for (adaptive) Newton-Cotes Quadrature

I am looking for practical error estimates for Newton-Cotes Quadrature rules. Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ...
7
votes
2answers
203 views

Finding a low-degree polynomial vanishing on half the zeroes of a polynomial system

Let $f(x)$ be a real polynomial of degree $2d$ without real roots. Let the complex roots be $z_1$, $\bar{z_1}$, $z_2$, $\bar{z_2}$, ..., $z_d$, $\bar{z_d}$ with $z_i$ in the upper half plane. Let ...
4
votes
0answers
167 views

Pair of two-variable polynomial equations of high order

I have the following pair of equations to be solved for two variables $\rho$ and $D$ resulting from a certain Maximum Likelihood Estimation for a time series $X_n > 0$, $n=0, \ldots, N+1$ with $N ...
3
votes
1answer
724 views

Parameter estimation for stochastic differential equation from discrete observations

Suppose we have a time-series $x(t_i)$ at discrete times $t_i$ and we want to estimate the parameters of an underlying SDE corresponding to this time-series: $$dx_t = f(x_t,\theta)dt + ...
2
votes
1answer
172 views

Possible pathological properties of positive definite matrix

Suppose $A$ is a positive definite matrix such that $$I \preceq A \preceq 1.01I.$$ Is it possible that $$\sum_{i=1}^n A_{1i}$$ can be arbitrarily large? Thanks, Jack
2
votes
0answers
131 views

A question on discrete numerical simulation on fluids mechanics

I read the paper "Stable, circulation-preseving simplicial fuids" by Elcott, et al: http://www.cs.jhu.edu/~misha/Fall09/Elcott07.pdf. It gives a structure preseving discretization of fluids. I have ...
6
votes
3answers
834 views

Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
7
votes
3answers
377 views

accelerating convergence of a class of sequences

Do any of the standard methods of acceleration convergence of series, when applied to the series $1 - 1 + 1/2 - 1/2 + 1/3 - 1/3 + ...$, give convergence to 0 with error $o(1/n)$? I tried applying ...
2
votes
2answers
384 views

What is the definition of an antilimit?

I've seen some references to antilimits in the numerical analysis literature, but no definition of the term. The impression I get is that in specific contexts where every sequence $x_0,x_1,x_2,\dots$ ...
1
vote
1answer
249 views

Understanding the rationale behind “batch means” estimation

Hello all, I am implementing an MCMC algorithm for my work, and I've come upon something in the literature which I just can't understand. Specifically, I am attempting to estimate the amount of ...
4
votes
0answers
137 views

Are there some numerical test to check if a map is a contraction?

Let's say I have a multivariate function $$ f:D \to D, D \subset \mathbb R ^n, D \text{ compact}, $$ for which there is no closed form. That is the only way to evaluate the function is to do it ...
4
votes
1answer
577 views

Numerical multivariate definite integration

I need to compute a set of multivariate definite integrals with infinite integration domain $$\displaystyle \int_{-\infty}^{\infty} \cdots \int_{-\infty}^{\infty} f(x_1,x_2, \ldots , x_n)\;\;dx_1 ...
2
votes
0answers
311 views

minimize a cost function with matrix traces

Hi, I have a cost function of the form $$F(X) = \operatorname{tr}(X'AX)+\operatorname{tr}(X'B),\quad\textrm{ s.t. }X'X=I.$$ $X$ is a $m\times n$ matrix, ($m>n$), with orthonormal columns. $A$ is ...
2
votes
1answer
97 views

non convex quadratic optimization

Hi I would like to optimize the following system: $$\min_{q,\|q\|=1} \sum_i^n |q^T M_i q|$$ More details: the size of the unknown vector q is $4\times 1$, M_i is a matrix of size $4\times 4$. It is ...
4
votes
3answers
406 views

Lower bound for sum of square root of the degrees of a connected graph

By Cauchy-Schwartz and the handshake lemma, it is easy to see that $\left( \sum_{i=1}^n \sqrt d_i \right)^2 \leq n \sum_{i=1}^n d_i =2mn$, with equality iff the graph is regular (constant degree). ...
1
vote
1answer
186 views

Discretizing a cosine function?

I'd like to start by noting that for some fixed natural $N$ basis functions for my system will be generated by $f(k,x)$ as defined and explained here or in numerous other sources: $$f(k,x) = \sqrt2 ...
0
votes
1answer
135 views

How to handle a scalar product in an integral?

I am having a problem with a certain inequality I try to understand. I think it's just a basic idia (/trick) I'm missing, but I can't seem to find it. Here's a simplification of the problem: $ ...
0
votes
0answers
73 views

Approximate closed-form solution for a recurrence

Find an (approximate) closed-form solution for $S(m, b)$. $$S(m,b)=\sum_{i=0}^{\lfloor (e-1)/2\rfloor}{e \choose i}S(m-1, b-i) \quad + \sum_{i=\lfloor (e-1)/2\rfloor+1}^{\min(b,e)}{e\choose ...
4
votes
0answers
218 views

Inadmissibility of Simpson's rule

(An earlier version of this at stackexchange got no answers.) Bayesianism says that all uncertainties, or at least all uncertainties about the truth or falsity of propositions, can be expressed by ...
3
votes
1answer
78 views

Conjugate gradient algorithm where first search direction is not equal to residual

In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact ...
33
votes
2answers
1k views

Recent fundamental new directions in PDEs

My main interests are in modern geometry/topology, algebra and mathematical physics. I observe that there is a raising communication, language and social barrier between this community and the ...
7
votes
1answer
177 views

Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method. In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...
11
votes
2answers
477 views

Computing a large permanent

Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix? I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...
3
votes
1answer
133 views

The discrete theory of compressible fluids dynamics

I am working on the discrete theory of compressible fluids dynamics, i.e., numerically solving and simulating the compressible fluids , we are interested in the way using discrete exterior calculus, ...
7
votes
1answer
166 views

Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?

Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...
3
votes
1answer
522 views

Stability in algebraic geometry

Suppose I have a collection of polynomials with multiple variables (more polynomials than variables, say), and I'm given noisy versions the values of these polynomials at a certain unknown point. I ...
10
votes
0answers
192 views

What are the difficulties in proving almost-everywhere stability of Gaussian elimination?

It is well known that Gaussian elimination without pivoting is numerically unstable, and in practice Gaussian elimination is done with row pivoting (partial pivoting). A theorem of Wilkinson states ...
5
votes
1answer
834 views

Efficient computation of Markov chain transition probability matrix

Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...
7
votes
0answers
608 views

American put option pricing by “binomial trees”

Dear MO World, I'm teaching a financial mathematics course and have found a fascinating (to me) numerical phenomenon and wonder if anyone has studied it, or knows anything similar. I'll try and give ...
10
votes
3answers
644 views

Rapid evaluation of multivariate normal integral

I'm implementing a model that requires me to numerically evaluate a multivariate normal integral of the following form $$\int_{-\infty}^\infty \phi(z)\displaystyle\prod_{i=1}^N \Phi(a_iz+b_i) \, ...
3
votes
1answer
154 views

Using Fourier Transform to speed up calculation of forces following an inverse square law

Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ...
15
votes
1answer
530 views

The Chow & Robbins game ≈ 0.79295350640: improvements could come from simple statistics, or from a continuous version of the game

This question seeks help with improving a numerical estimate of the value of the Chow and Robbins game. Much about this game is unknown, such as whether its value is rational, but there are two routes ...
1
vote
1answer
189 views

Dragilev method

What are the advantages and disadvantages of the Dragilev ( http://www.mathnet.ru/php/person.phtml?&personid=32359&option_lang=eng and ...
8
votes
1answer
404 views

Machin-like formulas for logarithms

I found this math puzzle blog post http://fredrikj.net/blog/2013/03/machin-like-formulas-for-logarithms/ which I'm reposting here with permission. I'm setting this to community wiki to minimize the ...
2
votes
0answers
78 views

Application and relevance of Sobolev gradients

The Sobolev gradient concept has been developed in the 1970s, with a first publication in 1985, and an introduction can be found at: Ranka I would like to learn how strong the impact of Sobolev ...
2
votes
0answers
76 views

Approximating solutions to minima of the discrete Lagrangian

I have been stuck on this problem for a week and I'm not sure whether or not it is hard or I'm just missing something obvious. General gist of the problem I have a variational problem on a ...
1
vote
1answer
814 views

Software to numerically solve partial differential equation

When we use software to numerically solve differential equation, for example, using finite difference, finite element or finite volume methods, etc., is it possible that people input differential ...
23
votes
3answers
1k views

“Wild” solutions of the heat equation: how to graph them?

It has long been known that the Cauchy initial-value problem for the classical heat equation on $\mathbb{R}$ (or $\mathbb{R}^n$) doesn't have unique solutions, without additional assumptions. In ...
2
votes
2answers
382 views

Computing hypergeometric function of matrix argument

In the context of the Bingham probability distribution the ${ }_1F_1$ hypergeometric function of matrix argument naturally arises as a normalization constant of the probability distribution function. ...
6
votes
2answers
294 views

Rigorous numerics for maxima and minima (one variable)

Let $f:\mathbb{R}_0^+\to \mathbb{R}$ be defined by some combination of the four basic operations and square roots. (The argument of square-roots is assumed is to be non-negative, and the value of ...
1
vote
1answer
222 views

integral basis of orthogonal complement

Suppose there are $r$ linearly independent vectors $v_1,\dots,v_r\in \mathbb{R}^n$, all of them have integer-valued entries and $\|v_i\|_\infty\leq m$ for some integer $m$. My goal is to find an ...
2
votes
0answers
249 views

eigenvalues of the sum of a stochastic matrix and a diagonal matrix

Let $D$ be a real diagonal matrix $D=diag(a_1,a_2,\ldots,a_n)$ with $a_1\le a_2\le\ldots\le a_n$. Assume that at least one of the $a_i$ is positive. Let $P$ be an irreducible, real, row-stochastic ...
3
votes
2answers
336 views

Questions on Discrete Exterior Calculus in numerial computing

I have several questions about the Discrete Exterior Calculus (DEC) in the numerical method for solving partial differential equation in physics: (Discrete Exterious Calculus is the newly developed ...
1
vote
1answer
127 views

For what values of the parameter does this function have an elementary anti-derivative?

I am a grad student working on some independent research trying to derive some exact formulas for a particular class of power series. During my study I came across the following integral which would ...
2
votes
1answer
185 views

Reducing the error of Algorithms by assigning variables formulas instead of values

Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways: 1- Mark ...
4
votes
1answer
506 views

Hilbert Matrix and Approximation Theory

I was reading about the Hilbert matrix and Cauchy determinants: \[ \det \left[ \frac{1}{i+j-1} \right]_{i,j} \] By guessing where this determinant is $0$ or $\infty$ we can guess the right formula. ...