All Questions
1,732 questions
6
votes
1
answer
4k
views
Weyl inequalities for largest eigenvalue of matrix sum
The $k^{\rm th}$ largest eigenvalue (arranged in decreasing order) of the sum of two $N \times N$ Hermitian (real symmetric) matrices $\bf{A}$ and $\bf{B}$ can be stated using the Weyl inequalities as
...
- 385
6
votes
1
answer
609
views
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...
- 1,183
6
votes
1
answer
861
views
Is Binary Integer Linear Programming solvable in polynomial time?
The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...
- 221
6
votes
1
answer
877
views
Is $O(10^{-6})$ an acceptable notation in numerical analysis? [closed]
The following question has been on math.SE for several days. Without having a satisfying answer, I'd like to ask the experts here.
In mathematics, the big $O$ notation is used to describe the ...
user14319
6
votes
3
answers
11k
views
Maximum flow with negative capacities?
I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient ...
- 83
6
votes
1
answer
239
views
Numeric equality testing?
Suppose we have two closed-form expressions with $k$ unknowns which are hard to test for equality but easy to evaluate numerically over $\mathbb{R}^k$. One could then approach the problem of equality ...
- 2,442
6
votes
1
answer
234
views
Stopping criteria for damped Newton iterations with backtracking line search
Are there better criteria than the Armijo criterion for damped Newton iteration with backtracking line search, when the objective is standard self-concordant? (See Boyd and Vandenberghe.)
Let $F(x)$ ...
- 981
6
votes
1
answer
779
views
If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?
I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...
6
votes
4
answers
1k
views
Applications of Hodge-de Rham Laplacian on p-forms ($p\neq 0,n$) in physics or engineering
The Hodge-de Rham Laplacian $L=(d+d^*)^2$, where $d$ is the boundary operator of the de Rham complex, is well-known in the math community. Recently, I tried very hard to search for examples of its use ...
- 473
6
votes
3
answers
854
views
Error in Polynomial Root Finding Algorithm with Synthetic Division
I have written a program which finds the roots of polynomial using Newton's Method. After finding the first root to within a tolerance (note that this also finds complex roots), I use synthetic ...
- 163
6
votes
1
answer
737
views
Rank of the absolute-value matrix $|M|$ vs. rank of $M$
Let $M$ be a real matrix of rank $r$ (and let us set $M=UV^T$, with $U,V^T\in\mathbb{R}^{n\times r}$, to fix the notation).
Let $|M|$ be the matrix obtained by taking the absolute value of each entry ...
- 20.2k
6
votes
4
answers
2k
views
Quantitative de Moivre–Laplace theorem (reference request)
The classical de Moivre-Laplace theorem states that we can approximate the normal distribution by discrete binomial distribution:
$${n \choose k} p^k q^{n-k} \simeq \frac{1}{\sqrt{2 \pi npq}}e^{-(k-np)...
- 4,729
6
votes
1
answer
222
views
Computing $(AA\otimes BB + AB \otimes BA)^{-1}$
Can anyone suggest a way to numerically compute the following matrix vector product?
$$u=A^{-1}b=(AA\otimes BB + AB \otimes BA)^{-1}\operatorname{vec}(C)$$
Here $AA,BB,AB,BA$ and $C$ are $d\times d$ ...
- 2,442
6
votes
2
answers
1k
views
Is the matrix positive definite given the Gauss-Seidel method converges?
I know that the Gauss-Seidel method converges given that the matrix you want to solve is symmetric positive definite. However, I'm wondering if the "converse" of the statement is true. Namely, if $A$ ...
- 205
6
votes
1
answer
797
views
Celestial mechanics and Runge Kutta methods
I am working on an example here to simulate the orbit of Earth for one year.
As you can see in the notebook, RK45 doesn't conserve energy, and after one simulated year it has spiraled in substantially....
- 61
6
votes
1
answer
415
views
Difference stencils approximating Laplacian
Let $\Delta$ be the Laplace operator on the interval $[0,1]\subset \mathbb{R}$.
Divide $[0,1]$ into small intervals of size $h$ to get an equidistant grid. One can approminate $-\Delta$ on this grid ...
- 161
6
votes
4
answers
633
views
Expected value of a function over random sets
I am doing an analysis on the complexity of some set-related algorithm where the input is a random set. One of my setbacks can be formulated as follows:
Pick $k$ distinct numbers out of numbers $[1,n]...
- 396
6
votes
2
answers
973
views
Divergence of the Lagrange interpolation on the Chebyshev nodes
Faber theorem states that for every $\lbrace x_k^{(n)} \rbrace$ there exists a continuous function $f$ such that $\| f - L_n \|_{\infty} \not\rightarrow 0$, where $L_n$ is an interpolation polynomial ...
- 109
6
votes
1
answer
1k
views
Arnoldi method to compute the dominant eigenvector
Hi, everyone!
I have a problem of computing the dominant eigenvector. When I want to approximate the dominant eigenvector of a large sparse matrix via the famous Arnoldi method, I am wondering how to ...
- 61
6
votes
2
answers
993
views
An orthogonal companion matrix
Let $P\in{\mathbb R}[X]$ be a monic polynomial with roots on the unit circle. For the problem below, we may assume wlog that the roots are simple and distinct from $\pm1$. It can be shown that there ...
- 52.3k
6
votes
3
answers
490
views
Non-polynomial splines, a non-linear problem
I'm looking for references on how to construct spline-like functions from a basis that does not include piecewise polynomials.
To be specific, given a class of functions such as "decaying ...
- 3,065
6
votes
3
answers
615
views
What is the current fastest method to calculate Lerch's Phi transcendent?
Lerch's Phi transcendent is
$$
\Phi(z,s,a) = \sum_{k=0}^{\infty} \frac{z^k}{(k+a)^s}
$$
I am trying to compute this for the following parameters:
$z$ is complex, $|z| \approx 1$ and $|z|$ < 1 (...
- 4,897
6
votes
1
answer
218
views
Any convergence rule for ${\mathbf X}_k={\mathbf A}{\mathbf X}_{k-1}{\mathbf B}$?
We know iteration ${\mathbf X}_k=\mathbf{A}{\mathbf X}_{k-1}$ converges if the spectral radius of $\mathbf A$ is smaller than 1 (see here). Is there any known rule for iteration ${\mathbf X}_k={\...
- 272
6
votes
2
answers
834
views
Symmetric matrix formula for Gauss-Legendre quadrature
While searching the web, I came across the following algorithm for the Gauss-Legendre quadrature. I wasn't able to find a reference or a proof of my own as to why it works. I'll present it, and the ...
- 3,574
6
votes
1
answer
378
views
Compensated compactness for system of conservation laws?
As far as I knew, the method of compensated compactness can be used only for one-dimensional scalar and $2\times 2$ systems of conservation laws, i.e. $u_t+f(u)_x=0$. But if I understood correctly ...
- 105
6
votes
1
answer
217
views
numerically track spectrum curves of a parameter dependent linear operator
Hi, I am interested in how to numerically track spectrum curves of a parameter dependent linear operator.
Given a linear operator in square matrix form $M(t)$, where the matrix is smooth dependent of ...
- 135
6
votes
1
answer
155
views
Adding constraints as penalty with $\| \cdot \|_0$ norm
In the paper Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries (page 2), the authors rewrite the minimization problem
\begin{align}
\min_{\alpha \in \mathbb R^k} \| \...
- 113
6
votes
1
answer
263
views
Algorithm that solves every Mixed Integer Linear Program (to optimality)?
Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically?
I know that you usually ...
- 1,282
6
votes
1
answer
216
views
Estimates of Hausdorff dimension (and its derivatives)
For example, the cookie cutter maps, say $T:I_1 \cup I_2 \subset [0,1] \to [0,1] $ is a $C^2$ map such that $|T'|>1$ and provided $I_1$ and $I_2$ are disjoint closed intervals and $T(I_i)=[0,1]$. ...
- 165
6
votes
1
answer
218
views
Approximating an iteratively defined function
Let $f_0,f_1,\ldots$ be a sequence of functions $f_n : [0,1] \rightarrow R$ defined as follows:
$$f_0(x) =1+2x$$
$$f_{n}(x) := \left\{\frac{5+t}{2} : \text{ where t solves } f_{n-1}\left(\frac{x}{t}...
- 13k
6
votes
2
answers
3k
views
Computational complexity of integration in two dimensions
I have an algorithm for solving a certain problem that requires that I compute two-dimensional integrals as a subroutine, and I'd like to make some kind of statement about its running time. Suppose $...
- 93
6
votes
2
answers
2k
views
Computation of a Drazin inverse
I need to compute the Drazin inverse $A^D$ of a singular M-matrix $A$, i.e., a matrix in the form $A=\lambda I -P$, where $P$ has nonnegative entries and $\lambda$ is the spectral radius (Perron value)...
- 20.2k
6
votes
1
answer
1k
views
Frozen coefficient method (von Neumann stability analysis)
Earlier it was considered that frozen coefficients method for Neumann stability analysis for finite difference scheme is more heuristic than rigorous. But I have read some information in a book by ...
- 161
6
votes
2
answers
2k
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$$
...
6
votes
1
answer
443
views
Algorithm for numerically approximating the Prokhorov metric?
Question: What is known about algorithms for numerically computing/approximating the Prokhorov distance between two measures?
Recall that the Prokhorov distance metrizes the topology of weak(-*) ...
- 1,160
6
votes
1
answer
1k
views
Condition number for a symmetric positive definite matrix
I am trying to get an estimate for the induced 2-norm condition number $\kappa_{2}(M)$ of this matrix $M$:
$$M_{ij} = \frac{1}{(n-i)!(n-j)!(2n-i-j+1)} = \displaystyle\int_{0}^{1}\frac{x^{n-i}}{(n-i)!} ...
- 1,538
6
votes
1
answer
1k
views
Speed up Linear programming
I have a linear programming problem like this:
minimize $c^t X$
under the constraint that $AX \ge b$.
I will need to solve this linear programming problem online many times. I need it to be as fast ...
- 83
6
votes
1
answer
1k
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 ...
- 63
6
votes
2
answers
660
views
analytic approximation of a non-negative matrix by a sequence of positive matrices
Let $L \in \{0,1\}^{n \times n}$ be a non-negative matrix whose row sum is 1. ($L$ stands for "limit"). It is known that there exists a unique $r \times r$ principal minor of $L$ that is a permutation ...
- 1,010
6
votes
0
answers
233
views
Newton type method for finite fields?
I have a polynomial $p(x)$ in $\mathbb{Z}/q\mathbb{Z}$ that is easy to compute for any $x$ but has an absurdly large degree $d > 2^{256}$. I know for a fact that it has a zero and I would like to ...
- 591
6
votes
0
answers
137
views
Why wavelet methods are not popular anymore in nonparametric statistics?
Back in my master years, I took a nonparametric statistics class. In this class, a few nonparametric methods were presented, but I remember spending a lot of times on methods based on wavelet ...
- 73
6
votes
0
answers
197
views
Where to cut off a double sum?
I have to compute a double infinite sum to within a given accuracy $\epsilon$. Let us say the sum is of the form
$$\sum_{m\geq 1} \sum_{n\geq 1} \frac{a_{m,n}}{m^2 n^2 \max(m,n)},$$
where $|a_{m,n}|\...
- 20.2k
6
votes
0
answers
394
views
Numerical analysis with p-adic numbers
How should one go about doing numerical analysis with $p$-adic numbers?
By that I mean, how should one go about implementing numerical integration (using analogues of Newton-Cotes or perhaps Gaussian ...
- 3,065
6
votes
0
answers
320
views
Can we approximate any eigenvalue of an infinite matrix via eigenvalues of some sequence of submatrices which approximates the matrix?
Let $T:\ell^2\to\ell^2$ be a compact linear operator. Let $[T]=(a_{i,j})_{i,j=1}^{\infty}$ be the representing infinite matrix of $T$ with respect to the canonical base. Let $T_n$ be the finite rank ...
- 596
6
votes
0
answers
206
views
Degree of Chebyshev polynomial necessary
In general, given $0<a<1$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[1-\frac{a}2,1+\frac{a}2]$ at every $x\in[1-a,1+a]$ and $f(0)=0$. What is minimum degree that is ...
- 13.9k
6
votes
0
answers
97
views
Finding the optimal mixture of two convex functions
I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...
6
votes
0
answers
379
views
Numerical Methods for stochastic PDE, from rough paths to backward equations
this question is about some literary references regarding the state of the art in terms of numerical methods for SPDE's. In particular,
Have the numerical implications, if any, of the results in ...
- 254
6
votes
0
answers
317
views
Variant of orthogonal Procrustes problem
The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$ and $B$ are $n\times d$. Geometrically, $M$ rotates a set of ...
- 61
6
votes
0
answers
565
views
What are the eigenvectors of the Lagrange interpolation matrix?
Let $F$ be a field.
Let $x_1,\ldots,x_k,y_1,\ldots,y_k\in F$ be distinct elements in the field.
Consider the $k\times k$ matrix that in position $i$, $j$ has the element
$\frac{\prod_{l\neq i}(y_i - ...
- 179
5
votes
4
answers
2k
views
Determining a recurrence relation
I would like to solve the general problem of determining a linear recurrence relation that fits a given integer sequence of length $n$, or stating that none exists (with fewer than $n/2-k$ ...
- 9,114