Questions tagged [computational-mathematics]
This tag concerns computational problems central to mathematical and scientific computing. The scope includes algorithms, numerical analysis, optimization, and linear algebra, computational topology, computational geometry, symbolic methods, and inverse problems.
1,950
questions
0
votes
0
answers
19
views
Minimizing a function involving a gamma function
In one of the proofs about some estimates of upper bounds of zeros of the Riemann zeta function I am studying, I have a function that looks like
$V(\alpha, x, \delta,T)= \alpha e^{2\alpha(\frac{1}{T} +...
- 11
0
votes
1
answer
80
views
Finding the circle that is at the minimum distance from all randomly generated points. [closed]
Suppose I have randomly generated points in a 2-D plane, and I want to find a circle that is at the shortest distance from all points. That is, I want to find the minimum of the maximum distance for ...
- 17
-2
votes
0
answers
27
views
Can a non-analytic function provide analytic solution (i.e., exact solution)? [closed]
What is an analytic function?
What is an analytic solution?
These two terms have the same meaning?
If no, can a non-analytic function provide an analytic solution?
- 1
1
vote
0
answers
40
views
Does series acceleration improve computational efficiency?
There are several methods of series acceleration.
For example, Euler's transform is:
$$\sum_{n=0}^\infty (-1)^na_n=\sum_{n=0}^\infty \frac{(-1)^n}{2^{n+1}}\sum_{k=0}^n (-1)^k {n \choose k} a_{n-k}$$
...
- 11
0
votes
0
answers
22
views
Improving the condition of a system of equations
I am trying to understand by hand how balancing a matrix increases the stability of procedures like solving a system of equations. The balance procedure that I am following is here, I also found ...
- 123
0
votes
0
answers
38
views
Is there a difference between combinatorics and combinatronics? [closed]
I've read articles about combinatronics, but also see articles about combinatorics. Is this just a typo? Or are these two different subspecialties in mathematics, and if so, what does each include/...
0
votes
0
answers
17
views
Let L = {1^s| such that there exist s consecutive 1s in the (decimal) expansion of π}. Is the language L Turing-decidable?
Let $L = \{1^s|$ such that there exist $s$ consecutive 1s in the (decimal) expansion of $\pi\}$.
Is the language $L$ Turing-decidable?
At first glance it seems like it would not be Turing-decidable ...
0
votes
0
answers
24
views
Lanczos algorithm for two-dimensional vector space $\mathcal{H}_1\otimes \mathcal{H}_2$
Consider the Hamiltonian $H_1$ (Hermitian matrix) along with initial state $|\psi_1\rangle$ which can be used to generate the vectors
$$\mathcal{K}_1 = \{H^n_1|\psi_1\rangle : n=0,1,2,\ldots \}$$
The ...
- 516
0
votes
0
answers
8
views
Properties of a "generalised" little-o notation
According to Wikipedia, the little-o notation is defined this way: $f(x) = o(g(x))$ as $x\to\infty$ if for all $\varepsilon >0$ there exists $N\in \mathbb{R}$ such that
$$ |f(x)| \le \varepsilon g(...
- 300
0
votes
0
answers
13
views
Derivation of Q in EM algorith
Trying to learn EM Algorithms. Can someone explain the derivation steps they took to go from step 4.1 - 4.3. I am quite new to computational stats and it feels like I may be missing some fundamental ...
- 21
-2
votes
0
answers
43
views
Establish (proof!) the laws of arithmetic with type theory:
Here we define the (×), (+) and (→) types.
We have to define two functions one function left to right and vice-versa. For each transformation, if I transform and then transform the transformation back ...
1
vote
0
answers
44
views
Minimal Simplicial Complex from a Sequence of Betti Numbers
I found the following problem in a Computational Topology course that I am following: Write an algorithm that given a sequence $(\beta_0,\ldots,\beta_d)$ of integers builds a simplicial complex whose $...
- 115
16
votes
3
answers
964
views
One of the numbers $\zeta(5), \zeta(7), \zeta(9), \zeta(11)$ is irrational
I am reading an interesting paper One of the numbers ζ(5), ζ(7), ζ(9), ζ(11) is irrational by Zudilin. We fix odd numbers $q$ and $r$, $q\geq r+4$ and a tuple $\eta_0,\eta_1,...,\eta_q$ of positive ...
- 536
0
votes
0
answers
22
views
simultaneous iteration fails for the 1d laplacian operator?
The code below is to use the simultaneous iteration method to calculate the eigenvalues of the 1d Laplacian operator. The exact eigenvalues are known analytically.
It is strange that there is no ...
- 1,005
0
votes
1
answer
13
views
finite steps to Hessenberg form and/or triangular form
I am learning numerical linear algebra and curious about one thing. It is possible to reduce any matrix to the Hessenberg form in finite steps with a unitary matrix. But why is it impossible to reduce ...
- 1,005
0
votes
1
answer
19
views
Is the Asymptotic complexity of the find max algorithm O(n) or O(n^2)?
Algorithm pseudocode:
1 def find max(data):
2 biggest = data[0] # The initial value to beat
3 for val in data: # For each value:
4 if val > biggest # if it is greater than the best ...
1
vote
0
answers
20
views
Prove the optimal property of an orthogonal projection method -- how to show that the approximate solution minimizes the *A-norm* of the error?
Given an orthogonal projection method (when $K = L$) and a symmetric positive definite (SPD) matrix $A$, show that $\tilde{x}$ minimizes $(A(x−x^*),(x−x^*))≡ \|x - x^* \| ^{2} _A = ( A ( x − x^* ) , ...
- 11
11
votes
1
answer
230
views
Beautiful errors in graph of $\sin(x^2+y^2)$
I was writing a simple program to help visualize inequalities based on 2 variables. The test inequality that I was using was this: $$\sin\left(0.1(x^2+y^2)\right)\geq0$$
Regions that satisfy the ...
- 1,204
-1
votes
1
answer
40
views
If a matrix is an outer product of two vectors; can I determine the vectors? [closed]
I am working with floating point numbers. There is a 3x3 matrix that has determinant 1e-14.
I have reason to believe this matrix is an outer product of two vectors. If the assumption is correct, how ...
- 131
0
votes
0
answers
16
views
Hardy-Littlewood maximal function algorithm
There exists implemented algorithm which compute the Hardy-Littlewood maximal function at least for reasonably simple non-trivial cases? E.g. piecewise linear functions?
- 330
1
vote
1
answer
30
views
How do we find the weights for finite differences?
My professor gave us this question to solve, but I don't know have much familiarity with the topic.
Question
The forward difference is first order accurate and is defined to be $$ D_{+} = \frac{f(x+h) ...
- 347
2
votes
1
answer
80
views
Confusion about atan vs atan2
I have the following function:
$$f(\omega) = \arctan\left(\frac{-\omega\cdot R / L}{-w^2 + 1/(C\cdot L)}\right)$$
When I try to plot it (atan(f(w))), I get the ...
- 131
0
votes
0
answers
23
views
Investigating the numerical accuracy of a truncated Legendre polynomial expansion of an unknown function
I have an integral equation involving an unknown function $f(x)$, of the most basic form
$$
\int_{-1}^{1} e^{iω(t) x} f(x) \ dx = g(t)
$$
I am solving for an approximation of $f(x)$ by substituting in ...
- 15
0
votes
0
answers
58
views
algorithm guaranteed to converge for convex function
I have a multi-variate convex function, and I want to find its global minimum. We know there is one and only one minimum.
Is there any algorithm which is guaranteed to converge to the minimum starting ...
- 1,005
0
votes
0
answers
18
views
Need help with proving energy stability of forward Euler for heat equation
I have the 1D heat equation $u_t= \alpha u_{xx}$ on $x \in [0,1]$.
It has homogeneous Dirichlet boundary conditions.
I intend to use the forward Euler numerical scheme.
$$\frac{u^{n+1}-u^{n}}{k} = \...
0
votes
0
answers
45
views
Is there a way to find if there relationship of numbers
I have a challenge. This may be little tricky or even not possible but wanted to check if anyone has any thoughts on this?
PS : This question is in general and not related to only to R. May be I can ...
- 111
0
votes
1
answer
58
views
verifying Ramanujan constant
The famous Ramanujan constant $ e^{\pi \sqrt{163}} $ is a near-integer.
see the link here.
I tried to calculate this number with matlab and failed. Matlab cannot even deliver the first 9 apparently ...
- 1,094
2
votes
1
answer
52
views
Is it possible to find something better than binary search for this problem?
Let's say we have $n$ urns (numbered $1$ through $n$) and the first $k$ urns have a ball in them (for some $k$ unknown to us) and the remaining urns are empty. Our goal is to determine $k$ by looking ...
- 1,363
0
votes
0
answers
30
views
Fast solvers for saddle-point problem (linear system)
I would like to speed up my multi body simulator. There, in every time step a linear system, often referred to as saddle-point problem, has to be solved. The system looks like this
$$
\begin{bmatrix}
...
- 285
0
votes
0
answers
17
views
Finding Maximum Value of Variable Using Only Its Fourier Transform?
Assume I have a variable u, which is an $m\times n$ array filled with exclusively real values. I want to find the maximum value within this ...
- 167
0
votes
1
answer
33
views
How to stop a negative exponential from rounding to zero?
I'm doing materials homework and calculating vacancy density, which has some large constants (Na and k), and have to do the function. the right side of the density equation is exp(-Q/(kT)), which ...
2
votes
1
answer
49
views
What is the time complexity of multiplying two matrices over an arbitrary ring?
I know that the time complexity of matrix multiplication over a field is well studied (multiplying two $n \times n$ matrices can be done in $n^\omega$ field operations, where $\omega$ is the matrix ...
- 141
0
votes
0
answers
50
views
Showing that an explicit s-stage RK method with its order of accuracy higher than s
I was asked to show an s-stage explicit Runge-Kutta Method cannot obtain accuracy higher than $s$. It suffices to consider autonomous system $y' = f(y)$ (otherwise by introducing a new variable $t$, ...
- 271
2
votes
0
answers
133
views
Which 2nd root finding method does the HP32E use to compute $Q^{-1}$?
The ancient pocket calculator HP32E computes $Q$, areas under the normal curve, with the "Algorithm 39" (same in FORTRAN) and the inverse $Q^{-1}$, quantile, using two different root finder. ...
- 309
0
votes
0
answers
24
views
generalized implicitly restarted lanczos method
I am looking for references on how to solve the generalized eigen-problem :
$$Ax = \lambda Bx \tag{1}$$
Where $A$ is a symmetric matrix and $B$ is symmetric positive definite.
I know a standard ...
7
votes
2
answers
255
views
When does $(a+b\sqrt n)^3+(a-b\sqrt n)^3=c^3$ have integer solutions $(a,b,c,n)$?
From this post Where Fermat's Last Theorem fails, we find the nice,
$$(18+17\sqrt2)^3+(18-17\sqrt2)^3=42^3$$
Using this initial solution, an infinite more can be generated using P. Tait's identity,
$$\...
- 54.7k
0
votes
1
answer
49
views
Is there a way for me to change the order of multiplying these matricies?
Given an equation of this form:
\begin{equation}
\vec{X}=\sigma(t) B^{-1}
\label{MasterEq}
\end{equation}
where $\vec{X}$ has the following components:
\begin{equation}
x_i=
\sum_{\alpha = ...
0
votes
0
answers
58
views
How do computers calculate irrational numbers? like how do they compute root 2? [duplicate]
I do know how to like get root 2 but it's the long division method, and from just seeing it I am genuinely confused how they would implement it. Then there is the prime factorization method but it ...
0
votes
0
answers
50
views
Given base $b$ what is the expected value of round off error in rounding to $d$ digits?
Given base $b$, what is the expected value of round off error (relative, not absolute) when we round $x$ to $d$ digits, where $x$ is a random variable? Assume $x$ is drawn from a uniform distribution ...
- 4,360
1
vote
1
answer
46
views
A special type of one symbol escape huffman code. Which source(s) will it be optimal for?
Background / Context:
The other day I implemented a special case of Huffman coding constructed with $2^{N}-1$ valid code words and 1 "escape" into a set of longer length codes.
As there is ...
- 25.9k
-1
votes
1
answer
76
views
Compute integral closure using a computer
Suppose given an inclusion $A\subset B$ of finitely-presented commutative algebras over a field. Is there a CAS which can decide whether $B$ is a finite $A$-module?
What if instead of f.p. k-algebras, ...
- 2,151
4
votes
0
answers
70
views
MVUE, Minimum variance unbiased estimator [duplicate]
Let $(X_{1},X_{2},\ldots X_{n})$ be a random sample from the distribution with density $$f(x)=\begin{cases}
e^{-(x-\delta)},&\text{if x > $\delta$}\\
0, &\text{otherwise}
\end{cases}
$$
...
- 183
1
vote
0
answers
59
views
A lower bound of the distance between 2 distinct roots of 2 distinct polynomials
Here is one of my homework in the computer algebra class:
Let $f(x),g(x)\in \mathbb{Z}[x]$ be of positive degree $m,n$, and $f(\alpha)=g(\beta)=0$, where $\alpha\neq \beta$ are real. Show that
$$ |\...
- 175
0
votes
0
answers
5
views
Navier Stokes FDM: Iterative Solvers (Component Form vs Matrix Form)
I hope you are all enjoying a pleasant holiday season, if you happen to be celebrating.
Currently, I am engrossed in a university assignment that involves conducting a benchmark with various solvers ...
0
votes
1
answer
38
views
Compare magnitude of integers with limited computation
I have a polynomial $f:\mathbf{Z}\to\mathbf{Z}$ and very large integers $n, x$ such that $f(n)\approx x$ (specifically, I can say that $f(n)$ is within some relatively small value $\epsilon$ of $x$). ...
- 283
1
vote
0
answers
16
views
Creating nonuniform grids for FDM with multiple points of concentration
If I am creating a grid in the $S_i$ direction with $N_S+1$ grid points. If I want more steps around some $K$, I can use:
$$
S_i=K+c \sinh \left(\xi_i\right), \quad i=0,1, \ldots, N_S
$$
where $c=\...
0
votes
2
answers
39
views
How can I use algebraical properties of group operations for generating subsets of blocks of binary numbers of same population count?
Considering blocks of binary digits, are from all binary numbers $\in \{0,\cdots,2^{N}-1\}$
Which operations can I define which will preserve the number of 1-bits in any given number? Is there some ...
- 25.9k
4
votes
1
answer
117
views
Evaluating $\lim_{n \to \infty} \frac{1}{n}\sum_{t = 1}^{n}e^{-k\cos^2(\omega t)}$, where $k>0$ and $0<\omega<\pi$
Need to evalute a closed form expression of the following limit:
$$\lim_{n \to \infty} \frac{1}{n}\sum_{t = 1}^{n}e^{-k\cos^2(\omega t)}$$
where $k>0$ and $0<\omega<\pi$.
Empirically, I have ...
2
votes
0
answers
104
views
Why does using $f(x)=x^2$ not work in Pollard's rho algorithm?
In Pollard's rho algorithm for integer factorization, we use pseudorandom sequences of the form $x_{i+1}=f(x_i)$ and look at them$\mod{n}$ until we get a cycle. Utilizing the birthday paradox, we can ...
- 146
-1
votes
1
answer
99
views
How to simulate from $dY_i=Y_i( \mu dt$ $+ \sigma_{(2)}( \alpha dB^{(1)}_i + \sqrt{1- \alpha ^2} dB^{(2)}_i))$ for $\mu, \sigma>0, \alpha \in [-1,1]$?
I am studying numerical methods from the textbook Monte Carlo Methods in Financial Engineering by Paul Glasserman and have encountered the following exercise:
I want to simulate from the stochastic ...
- 4,031