Numerical algorithms for problems in analysis and algebra, scientific computation

**0**

votes

**0**answers

10 views

### Dennis More' Superlinear Convergence_refrences request

Why in the proof of superlinear convergence of restricted broyden class (for the unconstrained optimization) we need the bounded deterioration condition for the approximation of all the true hessian ...

**10**

votes

**2**answers

348 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 abscisas and weights $\{ x_j, w^j \} _{j=1}^N$ for large $N\in\mathbb{N}$. My question is how to do it, ...

**-4**

votes

**0**answers

31 views

### basic proof in maths needed [on hold]

Let there are n distinct numbers like 1,5,9,12 etc. Now to derive the diversity, I want to find out:sum of square/square of sum of these numbers.
What is the proof or logic behind it? Can someone ...

**0**

votes

**0**answers

48 views

### Are these two difference scheme of the same differential equation equivalent?

I have been doing numerical simulation of the ODE below for days:
$$i\frac{dc_n}{dz} = -\sigma(c_{n+1}+c_{n-1})+(-1)^n\delta c_n$$
I tried two different difference scheme of this ODE, which in my ...

**7**

votes

**1**answer

89 views

### Fast Fourier Transforms for non-trigonometric bases

The fast Fourier transform allows decomposition into a sin/cos basis in $N \log(N)$ complexity. Can one generalize the algorithm (or the ideas used) to other bases, e.g. orthogonal polynomial bases ...

**1**

vote

**0**answers

44 views

### A centralised website for computational attemps in graph theory and metric geometry?

The set of questions below stems from this question.
1) does a website exist that contains (at least links to) code and data files, with the aim to centralise computational results in graph ...

**2**

votes

**2**answers

501 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$ ...

**5**

votes

**2**answers

205 views

### Alternating binomial Dirichlet series

I have come across the following deceptively simple expression:
$$ H_n^s=\sum_{j=1}^n(-1)^{j-1}\left(\begin{array}{c}n\\j\end{array}\right)j^{-s} $$
We have (using eg mathematica, though probably ...

**1**

vote

**1**answer

108 views

### Condition Number and CFL Condition in Finite difference Methods [closed]

when applying a Finite Difference scheme for an IVP, two factors come to mind when considering stability:
One factor would be the condition number of the approximation operator. The other factor ...

**3**

votes

**1**answer

82 views

### Symmetric matrix formula for Gaus-Legendre quadrature

While searching the web, I came across the following algorithm for the Gaus-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 ...

**4**

votes

**3**answers

232 views

### Quadrature formula max accuracy

I'm looking for a maximum accuracy quadrature formula:
$$
\int_{-1} ^{1} \sqrt{\frac {1-x}{1+x}} f(x)dx = A_1f(x_1)+A_2f(x_2)+R(f)
$$
I don't know exactly if it's Trapezoidal rule which has the ...

**2**

votes

**0**answers

69 views

### Deriving Milne's predictor of order four from extrapolation polynomial [closed]

I am trying to derive the following Milne's predictor formula of order four for the differential equation $\frac{dy}{dx}=f(x,y)$ from an extrapolation polynomial of degree four. $$y_{n+1} = ...

**6**

votes

**0**answers

214 views

### An inequality which involves a sum of integrals

Please help me to prove
$$
\sum\limits_{j=2}^n \frac{1}{j^\alpha (j-1)^\alpha} \int\limits_{j-1}^j \frac{dx}{x^{1-\alpha}(n-x)^\alpha} \leq \int\limits_0^1 \frac{dx}{x^{1-\alpha}(n-x)^\alpha},\quad ...

**4**

votes

**2**answers

69 views

### Euler Schemes in Stochastic Differential Equations

So i am trying to understand what happens in Implicit (backward) and Explicit (forward) Euler in Stochastic Differential Equations
I ll start with explicit. Say i have the following SDE known as ...

**-1**

votes

**0**answers

47 views

### Finding zeros of a function

I have a function of this kind
$$f(x)=\alpha+\beta \sum_i \frac{A_i}{x-B_i}$$
where $\alpha$, $\beta$, $A_i$ and $B_i$ are real numbers. I want to find numerically all the zeros of $f(x)$ (I want to ...

**1**

vote

**1**answer

104 views

### Looking for tighter bounds

I have to solve an equation which is $$\sum_{i=1}^N x_i = \sum_{i=1}^N y_i,$$ where
$$x_i = \frac{z_i}{1 + (K_i - 1) w}$$ and $$y_i = \frac{K_i z_i}{1 + (K_i - 1) w}.$$
The $z_i$ are all positive ...

**0**

votes

**0**answers

22 views

### Adaptive refinement of integral domain

In electromagnetics we need to calculate the radiated power which is defined as something like
$P_r=\int_0^{2\pi}\int_0^{\pi}R(\theta,\phi)\sin{\theta}d{\theta}d\phi$
We already have ...

**0**

votes

**1**answer

86 views

### Efficient computation of matrix exponential of trace zero matrix [closed]

I am looking for identities that may help with numerical computation of the matrix exponential ${\rm exp}(A)$ where ${\rm tr}(A)=0$. I am already aware of general-purpose algorithms for computing the ...

**4**

votes

**2**answers

264 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 ...

**2**

votes

**3**answers

598 views

### Solving a system of algebraic equations

I am trying to find complex solutions with positive real part $\{t_j \;|\;{\rm Re}\;t_j>0,
j = 1, 2, 3, \dots, n\}$ of the system of equations
$$0 = 1 + \sum_j \left(t_j^{2l+1} + ...

**5**

votes

**2**answers

1k views

### Algorithm for solving systems of linear Diophantine inequalities

So, I posted on StackOverflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...

**1**

vote

**1**answer

40 views

### Subquadratic multiplication of probability mass functions (with log-convolution?)

We are currently looking for a fast, i.e. subquadratic, algorithm for the following equation:
$z_m = \sum_{i,j :\, (i \cdot j) = m} x_i \cdot y_j$.
That is, we are given two finite input vectors $x$ ...

**1**

vote

**0**answers

57 views

### How to rotate a covariance matrix which contains quaternion elements? [closed]

I am implementing a paper which recovers full-3d body pose from images.
It represents individual body parts as 7D vectors containing first the absolute 3D location [x y z] and then the unit ...

**6**

votes

**2**answers

840 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 ...

**9**

votes

**1**answer

223 views

### How to compute $\sum_{x \in \mathbb{Z}^n} e^{-x^TMx}$ efficiently

Let $M$ be a real symmetric integer valued positive definite matrix with $\det(M) \geq 1$. I would like write code to compute
$$S_M= \sum_{x \in \mathbb{Z}^n} e^{-x^TMx}.$$
One option is to simply ...

**22**

votes

**9**answers

3k views

### What is… A Grossone?

Y. Sergeyev developed a positional system for representing infinite numbers using a basic unit called a "grossone", as well as what he calls an "infinity computer". The mathematical value of this ...

**0**

votes

**0**answers

47 views

### Separable Least squares - is there a notion of conjugate directions?

I have a general question.
Suppose I have the following to optimize
$$\|Y-A(\mathbf{x})B(\mathbf{y})\|^2$$
where $Y$ is a vector, $A(\mathbf{x})$ is a matrix that depends on a vector $\mathbf{x}$ in a ...

**4**

votes

**0**answers

148 views

### Efficiently calculate the trace of the product of two large but symmetric matrices, one of which is an inverse

Sorry about the long title. I need to calculate the trace of $M(M+D)^{-1}$, where $M$ is a dense symmetric matrix, and $D$ is a diagonal matrix. The main issue is the dimension could be large (usually ...

**0**

votes

**0**answers

25 views

### Circulant Block Sparse Matrix Least Squares

I have what boils down to a least squares problem that I am trying to exploit structure in order to calculate efficiently.
Consider a NxN circulant matrix A. Where the first row is ...

**5**

votes

**1**answer

214 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 ...

**4**

votes

**0**answers

51 views

### What does the Von Neumann's stability analysis tell us about non-linear finite difference equations?

I've asked this question on computation science stackexchange, but it did not receive any answers so I have decided to ask it here as well.
I am reading a paper [1] where they solve the following ...

**47**

votes

**8**answers

7k views

### There must be a good introductory numerical analysis course out there!

Background As a numerical analyst, I've frequently taught the 'Introductory Numerical Analysis' class. Such courses are found in many major universities; the audience typically consists of reluctant ...

**7**

votes

**1**answer

73 views

### Add a multiple of $I$ to a matrix to minimize its operator norm

Given $A\in\mathbb{C}^{n\times n}$, what is $s_* = \arg\min \|A-sI\|$?
Here $\|A\|$ is the operator norm, $\|A\|=\rho(A^*A)^{1/2}$, and $I$ is the identity.
The corresponding problem for the ...

**12**

votes

**1**answer

162 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 ...

**8**

votes

**1**answer

511 views

### How to evaluate binomial coefficients efficiently and as correctly as possible?

This question is more precisely about evaluation with a computer, of a binomial coefficient of the form $ \binom{x}{m}$ where $x$ is a real number and $m$ a rational integer.
The reason why I ask is ...

**50**

votes

**2**answers

3k views

### Recent observation of gravitational waves

It was exciting to hear that LIGO detected the merging of two black
holes one billion light-years away. One of the black holes had 36
times the mass of the sun, and the other 29. After the merging the
...

**1**

vote

**0**answers

13 views

### Maximization of the difference of a monotone submodular function and a linear function with a cardinality constraint

Maximizing a monotone submodular function with a cardinality constraint can be solved by using a simple greedy heuristic. However, if the submodular function is non-monotone, the greedy heuristic can ...

**1**

vote

**0**answers

17 views

### How can I filter the effects of a variable from a correlation matrix?

I have a correlation matrix (it contains 500 columns and 500 rows) and I would like to make an other correlation matrix in which one variable (and its influences) is filtered from the initial matrix. ...

**0**

votes

**1**answer

48 views

### Uniqueness and invariance of the LDLT decomposition

A real symmetric positive semi-definite matrix $A$ can be decomposed in the form
$A = P^TLDL^TP$,
where $P$ is a permutation matrix, $L$ is a lower unit triangular matrix and $D$ is a diagonal ...

**0**

votes

**0**answers

43 views

### Find optimal value for a regularization parameter in generalized eigenvalue problem

Consider the generalized eigenvalue problem :
$ \Sigma_{XY} \Sigma_{YX} {W} = \lambda \Sigma_{XX} {W} $
where $\Sigma_{XX} $ and $\Sigma_{XY}$ are sample covariance matrices are of the matrices ...

**1**

vote

**1**answer

385 views

### sign-flipping inverse

Consider this matrix:
$Z=\begin{bmatrix}23.9 & -7 & -17 \\\\ -7 & 23.9 & -17 \\\\ -17 & -17 & 33.9 \end{bmatrix}$
Its inverse is entrywise negative (you can check...) and ...

**2**

votes

**0**answers

338 views

### Fast inversion of a special kind of matrices - approximations are ok

Suppose I have a stochastic matrix $M$ (with thousands or millions of stochastic column vectors), which I split into two matrices: $D$ containing only the diagonal entries of $M$, and $R$ containing ...

**2**

votes

**0**answers

469 views

### Update the inverse of sum of two symmetric matrices

There are two invertible symmetric matrices A and B, of which B is a block diagonal. A and B have the same dimensions. I need to iteratively calculate the inverse of M = s * A + B, where s is a ...

**2**

votes

**0**answers

54 views

### What's the advantage of majorization-minimization (MM) algorithm [closed]

The majorization-minimization (MM) algorithm is a framework for convex and nonconvex optimization. When applied to nonconvex optimization, the MM algorithm solves a sequence of convex problems to ...

**5**

votes

**2**answers

1k views

### How to solve a fifth degree polynomIal

Charles Hermite have created a method using elliptic functions to solve fifth degree polynomial, to get around the theory of Galois. Can someone explain me it and give a simple example?
Tank you.

**0**

votes

**2**answers

377 views

### Discrete Wavelet Transform and L2 Basis

Using the mother wavlet $phi$ one obtains an orthonormal basis $\phi_{j,k}(x):=2^{j/2}\,\phi(2^j\,x-k)$of L^2 (on the unit interval say). Given a function $f$ on can calculate the coefficients using ...

**1**

vote

**0**answers

95 views

### Evaluate a Function to Full Machine Precision [closed]

If we want to evaluate $$f(x)=\frac{e^x-1-x}{x^2}$$ then we have to observe its large relative error as $x\to 0$.
My question is that how can we find a method so that we can compute $f(x)$ to full ...

**10**

votes

**2**answers

268 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 ...

**3**

votes

**3**answers

215 views

### Numerical solution of SDEs with colored noise

I am trying to numerically solve an SDE with both white and colored noise that models a non-linear circuit:
$$
dX_t = f(X_t) dt + \sigma_w dW + \sigma_c dC
$$
where $W$ is a standard Brownian motion ...

**0**

votes

**3**answers

608 views

### Numerical solution to Fisher-Kolmogorov equation

Can you use the Crank-Nicolson method to get a numerical approximation to the fisher-kolmogorov equation?
If not what would be the easiest way to model the equation using matlab?
Thanks and sorry its ...