All Questions
1,732 questions
15
votes
0
answers
398
views
References on Discrete field theory vs Discrete differential geometry vs Combinatorial topology
Let me ask several related questions on discretization of classical field theory:
In topological folklore, it is known that cochains are "discrete analogues" of differential forms, and coboundary ...
14
votes
14
answers
6k
views
Basic software libraries for numerical analysis using modern programming languages?
I'm looking for a software library with a scope similar to "numerical recipes", but implemented in a modern programming language. "Modern" in this context means to me: object oriented (not C or ...
14
votes
3
answers
1k
views
Accelerating convergence for some double sums
I am interested in the following general double sums, for integers $a\geq 1$ and $b\geq 2$,
$$Z(a,b) = \sum_{k,\ell \geq 0} \frac{2k+3}{\binom{k+2}{2}^a} \frac{2\ell+3}{(\binom{k+2}{2}+\binom{\ell+2}{...
- 3,587
14
votes
1
answer
2k
views
On the non-rigorous calculations of the trajectories in the moon landings
In a paragraph written by a person emphasizing that rigour is not everything in mathematics (I wish I had written down the details), it was stated that the moon landings would have been impossible ...
- 4,351
14
votes
3
answers
2k
views
Guaranteed correct digits of elementary expressions
Let $E$ be the set of elementary expressions, defined as the smallest set of mathematical expressions such that $1 \in E$, and if $a,b \in E$ then $a + b$, $a - b$, $ab$, $a/b$, $\exp(a)$, $\log(a)$ ...
- 361
14
votes
2
answers
1k
views
Who is Petrov of the Petrov-Galerkin method?
I was not able to find the origin of the name Petrov in the Petrov-Galerkin method for the numerical approximation of PDEs.
Wikipedia refers to a certain Alexander G. Petrov, but it is still not ...
- 837
14
votes
2
answers
2k
views
Rigorous numerical integration
I need to evaluate some (one-variable) integrals that neither SAGE nor Mathematica can do symbolically. As far as I can tell, I have two options:
(a) Use GSL (via SAGE), Maxima or Mathematica to do ...
- 20.2k
14
votes
2
answers
2k
views
Computing Gauss Legendre quadrature for large $N$
I've been scanning across the web, and haven't found a good method to compute the Gauss Legendre abscissas and weights $\{ x_j, w^j \} _{j=1}^N$ for large $N\in\mathbb{N}$. My question is how to do it,...
- 3,574
14
votes
1
answer
900
views
“Taylor series” is to “Volterra series” as “Padé approximant” is to _________?
Padé approximants are often better than Taylor series at representing a function. Given a Taylor series, one can use Wynn's epsilon algorithm to easily produce the Padé approximants to it.
Volterra ...
- 4,897
14
votes
2
answers
6k
views
What is the constant of the Coppersmith-Winograd matrix multiplication algorithm
Or at least it's order of magnitude.
I've only ever heard it described as "huge", and a google search turned up nothing.
Also, given that the Strassen algorithm has a significantly greater constant ...
- 2,383
14
votes
1
answer
1k
views
A mass spring model for hair simulation
A strand of hair is represented by a set of particles connected by springs.
The velocity for a particular particle is calculated implicitly using the following formula:
$\boldsymbol{v}^{n+1/2}=\...
14
votes
2
answers
606
views
Condition number of matrix after partial orthogonalization
I'm wondering about which bounds one can put on the condition number of
a $n\times n$ square matrix which is obtained from another $n\times n$
square matrix by orthogonalizing the first $m < n$ ...
- 141
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
13
votes
2
answers
664
views
Complexity of a weirdo two-dimensional sorting problem
Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
- 19.2k
13
votes
2
answers
14k
views
Closest point on Bézier spline
Given a two-dimensional cubic Bézier spline defined by 4 control-points as described in the Wikipedia entry, is there a way to solve analytically for the parameter along the curve (ranging from 0 to 1)...
- 243
13
votes
1
answer
1k
views
Regge calculus: Questions of consistency resolved?
Hello,
Regge calculus is an approximation scheme for General Relativity, which has been introduced in early-sixties and has been adopted both in numerical relativity and numerical quantum relativity. ...
- 5,327
13
votes
3
answers
835
views
Famous theorems that are special cases of linear programming (or convex) duality
The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...
13
votes
2
answers
946
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 ...
- 6,962
13
votes
2
answers
1k
views
Seeking proof for linear algebra constraint problem.
Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all ...
- 379
13
votes
0
answers
591
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 ...
13
votes
0
answers
458
views
Descartes rule of signs for a noncommutative polynomial in matrix variables
Recently, while studying certain notions of "averaging" a set of input matrices, I obtained a nonlinear polynomial in matrix variables. A simple example is
\begin{equation*}
\mathcal{G}(X) := X^n - \...
- 28.6k
13
votes
0
answers
1k
views
Constructive aspects of Caratheodory's theorem in convex analysis
Let me paraphrase Caratheodory's theorem in a probabilistic setup:
Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
- 1,839
12
votes
8
answers
1k
views
Why does randomness work in numerical algorithms?
There are successful numerical algorithms that involves a sequence of random numbers, like Monte Carlo methods or simulated annealing. I can follow the lines of proofs of their convergence, and ...
- 2,745
12
votes
6
answers
2k
views
Applications of group theory in numerical analysis?
Are applications of group theory known to exist in numerical analysis?
One particular aspect I am curious about is whether matrix groups have been successfully used to derive algorithms.
Also, are ...
- 1,302
12
votes
4
answers
989
views
Rounding errors in images of Julia sets
One typically computes Julia sets by iterating a complex function, such as a polynomial or rational function.
How do rounding errors affect the results?
I'm looking for references on this issue, ...
- 3,022
12
votes
8
answers
9k
views
Any good books on numerical methods for ordinary differential equations?
I need to find some masters-level exercises about numerical methods for solving ODEs. Are there any good references?
12
votes
1
answer
5k
views
Closest 3D rotation matrix in the Frobenius norm sense
Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...
- 561
12
votes
2
answers
5k
views
Why Householder reflection is better than Givens rotation in dense linear algebra?
It’s obvious that Givens rotation works better with sparse matrices. But I don’t know why Householder reflection is better for dense matrices. Does it require less computations? Or it’s numerically ...
- 253
12
votes
5
answers
9k
views
Solving Lyapunov-like equation
The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
- 121
12
votes
1
answer
991
views
The geometric-mean factorial
Think of the factorial as $f(n) = n \odot (n-1) \odot \cdots \odot 2 \odot 1$,
where $\odot$ is the binary operator for multiplication, $\cdot$. This suggests exploring replacing
$\odot$ with other ...
- 151k
12
votes
4
answers
3k
views
Is Gauss-Seidel guaranteed to converge on *semi* positive definite matrices?
I know that the Gauss-Seidel method is guaranteed to converge given that the matrix you want to solve is positive definite. I've looked at the proofs of convergence, and it appears that one cannot ...
- 123
12
votes
2
answers
8k
views
Is there a way to simplify block Cholesky decomposition if you already have decomposed the submatrices along the leading diagonal?
Let's say we have a block matrix $ M =\left( \begin{array}{ccc}
A & B\\
B^{*} & C \end{array} \right)$ where $M$ is positive definite. ($A$ and $C$ are also positive definite.)
There is a ...
12
votes
2
answers
3k
views
How to project a vector onto a very large, non-orthogonal subspace
I have a difficult problem.
I have a very large, non-orthogonal matrix $A$ and need to project the vector $y$ onto the subspace spanning the columns of $A$. If this were a small matrix, I would use ...
- 223
12
votes
1
answer
239
views
Interval arithmetic with different definitions of intervals
Interval arithmetic normally deals with intervals defined as $[a,b]$ with rules like $$[a,b]+[c,d]=[a+c,b+d]$$ I am interested in interval arithmetic with different interval definitions such as $$\{a\}...
- 497
12
votes
0
answers
599
views
Once differentiable, piecewise degree three polynomials on triangulated planar domains
Here is an easily described, but very difficult, problem that I
(and a number of other people) really would like to see solved during
our life times. The basic problem is to compute the dimension of ...
- 121
11
votes
2
answers
1k
views
Am I allowed to do non-rigorous numerical analysis?
I have a paper where I am trying to show that the growth of a certain function is exponential of the order $a^n$. I would like to compute $a$, at least approximately. The base $a$ satisfies a very ...
11
votes
2
answers
4k
views
Approximation of sum of the first binomial coefficients for fixed N
I'd like to compute $\sum_{i=0}^k {{N}\choose{i}}$. Is there a computable approximation for that?
- 111
11
votes
2
answers
964
views
Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?
Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...
- 1,826
11
votes
1
answer
2k
views
Did human computers use floating-point arithmetics?
Before the proliferation of computers in the 1950s, did human computers use floating-point formats for their computations?
Floating-point calculation was reportedly implemented already in the 1910s (...
- 5,327
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
11
votes
3
answers
2k
views
On mathematical studies of the Mpemba effect
Since the days of Aristotle and Descartes, it has been known that under certain circumstances warm water freezes faster than cold water. This effect is now commonly known as the Mpemba effect, named ...
- 1,482
11
votes
2
answers
2k
views
Multi-dimensional moment problem
Let $\mu$ be a measure on $\def\r{\mathbb{R}}\r^n$, $1\le n \le \infty$. Given a (finite) multi-index $\bar{i} = (i_1, i_2, \ldots)$, one can define the moment
$$ m_{\bar i} = \int x_i^{i_1} x_2^{i_2}...
- 12.8k
11
votes
3
answers
726
views
Can computers find zeros of order $2$?
We assume we are given an entire function $f: \mathbb C \to \mathbb C$ with $f(0)=1$ and $f'(0)=0$ and $f$ is real on the real axis.
We assume (as a fact about $f$, that we want to demonstrate ...
- 124
11
votes
3
answers
1k
views
Sampling from Sine Kernel and Airy Kernel
A determinantal process on the line is a random collection of points on $\mathbb{R}$ such that the probability of $x_1, \dots, x_n$ lying on the random set is $\det (K(x_i, x_j))_{(i,j)}$. Examples ...
- 22.8k
11
votes
2
answers
4k
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 + \sigma(x_t,\...
- 840
11
votes
1
answer
3k
views
Best way to find a closest vector in a lattice
Let $v_1,\dotsc,v_n$ be linearly independent vectors in $\mathbb{R}^n$, and let $\Lambda=\bigoplus_{i=1}^n \mathbb{Z}v_i$. The question is, given a vector $w$ in $\mathbb R^n$, find the element $v$ ...
- 351
11
votes
1
answer
713
views
Weakest condition for an integrable, almost-symplectic manifold?
I was recently speaking with someone who works in Computational Chemistry and they mentioned that in a lot of the computational simulations they do, they have systems that are not symplectic but still ...
- 515
11
votes
1
answer
420
views
The complexity of the leading fractional bit of a power of a rational number
On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are ...
- 4,636
11
votes
2
answers
1k
views
Existence of sparse LU decomposition of sparse matrix
Let $A$ be a sparse matrix over some field. I would like to know about the existence of LU decompositions so that $L,U$ are both sparse.
More precisely, let $A$ be an $N$-by-$N$ matrix. Suppose each ...
- 547
10
votes
5
answers
16k
views
Numerical differentiation. What is the best method?
What is the best method for 1D numeric differentiation? Something as glorious as Gaussian quadrature for numeric integration.
Maybe differential quadrature is such a method? What is its accuracy?
I'...
- 441