This tag concerns computational problems central to mathematical and scientific computating. The scope includes algorithms, numerical analysis, optimization, and linear algebra, computational topology, computational geometry, symbolic methods, and inverse problems.

learn more… | top users | synonyms

1
vote
1answer
70 views

another counting problem

There are $k$ warriors that participate in the Wars, which have happened for the past $n$ years. Each year there has been a victor. Further, a particular warrior $W$ has won the Wars an even number of ...
1
vote
1answer
69 views

A problem on GCD

I want to calculate $f(n)$ where $f(n)$ is given by $$f(n) = \sum_{i=1}^n \dfrac{n}{gcd(n,i)}$$ and $2\leq n\leq 10^{12}$. Can someone tell me the fastest algorithm to calculate this. thanks
0
votes
1answer
68 views

Deleting subsets in the list of sets

If we have a list like $[[2,1],[5,2,1],[6,5,2,1],[9,10]]$ and I want to find the result in the form of $[[6,5,2,1], [9,10]]$ and want to delete all those list that are contained in another. How may I ...
1
vote
2answers
113 views

How can I solve this problem without having to do it by hand?

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement without forcing me to do it ...
0
votes
1answer
78 views

How can I solve this problem without doing it by hand? [duplicate]

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement without forcing me to do it ...
1
vote
2answers
104 views

Is there any way to solve this problem without having to do it by hand? [duplicate]

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement. Is there any way to group ...
3
votes
0answers
26 views

Has there been work on computational group theory applications to computing colimits of crosses n-cubes of groups?

I'm trying to compute homotopy groups of a few spaces using crossed n-cubes of groups. I'm able to describe a few colimits in terms of quotients of induced crossed modules and nonabelian tensor ...
3
votes
0answers
408 views

Nerve Theorem: Is the finite union of closed convex sets triangulable?

My Question: Let $A_1, \ldots, A_k \subseteq \mathbb{R}^n$ be closed convex sets. Is the union $\bigcup_{i=1}^k A_i$ triangulable$^1$? If so, why? Background: I'm trying to better understand the ...
0
votes
1answer
201 views

Is there any algorithm (if possible, I need the codes) for Jordan normal form decomposition for large matrices in practice?

Although it is an ill-posed problem as B Kågström said in "An algorithm for numerical computation of the Jordan normal form of a complex matrix", I wonder what people do when they need to do Jordan ...
0
votes
1answer
36 views

Eliminate $p$ from these 2 equations.

$$ X \ = \ 2 \left[ \dfrac {h_1pv_1} {(1-p^2v_1^2)^{1/2}} + \dfrac {h_2pv_2} {(1-p^2v_2^2)^{1/2}} \right] \\ T_2 \ = \ 2 \left[ \dfrac {h_1/v_1} {(1-p^2v_1^2)^{1/2}} + \dfrac {h_2/v_2} ...
2
votes
1answer
113 views

Going through all Bit Strings with no 11 in it (no consecutive 1s)

My question is very simple: How can i (efficiently) go through all Bitstrings which don't contain two consecutive 1s? So for instance, all Bitstrings of length 3 with no consecutive 1s are: 000, 001, ...
1
vote
3answers
124 views

For how many consecutive numbers Collatz conjecture was checked?

I heard here that Collatz conjecture was checked at least for every first $5 \cdot 10^{18}$ natural numbers, but I cannot find any source or actual information about this. Can anyone help to find out ...
1
vote
2answers
205 views

Questions about the field scientific computing

I have heard about the field of Applied and Computational Mathematics, Scientific Computing and want to get some information. Is this a combination of computer science and mathematics? What subjects ...
1
vote
2answers
64 views

How to compute the sine of a complex number in floating-point arithmetic?

What is the most efficient way to numerically compute the sine of a complex number? Suppose I want to calculate the sine of a complex number a + bi on a computer. Suppose that a and b are both ...
1
vote
1answer
40 views

Approximating zeros on an interval

I'm writing a program for my AP Calculus class, and I'm trying to write an equation solver that approximates the zeros of functions. Right now it can take symbolic derivatives and evaluate functions. ...
1
vote
0answers
101 views

QR decomposition: Same results for Classical Gram-Schmidt and Modified Gram-Schmidt

I am implementing QR decomposition (in Fortran) for a complex-valued matrix, using Classical Gram-Schmidt and Modified Gram-Schmidt (and Householder). I was expecting that the Classical Gram-Schmidt ...
1
vote
1answer
136 views

Rational approximation of $\tanh\,(\sqrt[4]{s}$)

I'd like to find a rational representation of $$f(s) = \frac{\tanh\,\sqrt[4]{s}}{\sqrt[4]{s}}= \frac{a_0 + a_1 s + a_2 s^2 + ... + a_n s^n}{b_0 + b_1 s + b_2 s^2 + ... + b_m s^m} $$ For the case ...
0
votes
1answer
59 views

Practical differences between a PRNG and a Markov chains

In computer programming you can easily find people describing both a PRNG, like a Mersenne Twister, and a Markov / Stochastic process as "pseudo random generators". I honestly never liked this ...
0
votes
0answers
29 views

Numerical calculation of an $x$ for which $\pi(x) > li(x)$

Littlewood 1914 proved that there are an infinite number of $x$ for which $\pi(x) > li(x)$. Skewes 1933 provided the first numerical upper bound on $x$ ...
-1
votes
1answer
91 views

Fermat Last theorem on Poly-Euler numbers

The poly-Euler numbers, denoted as $E_{n}^{(k)}$, are defined by the following generating functions :$${2\operatorname{Li}_k(1-e^{-x}) \over 1+e^{-x}}=\sum_{n=0}^\infty E_n^{(k)}{x^n\over n!}$$ The ...
0
votes
2answers
35 views

Design a DFA with following condition.

A DFA that accepts a language in which every odd position of a string is a 1 with inputs as {0,1}
1
vote
1answer
112 views
0
votes
1answer
43 views

How is the status of a bigger number known while the smaller not?

In this wolfram mathworld article in the table below the status of $2059$ is known before the some smaller numbers, or they choose to aim the computation for that specific number?
7
votes
1answer
769 views

Why is Householder computationally more stable than modified Gram-Schmidt?

I'm having trouble nailing down why using Householder transformations yields a more stable/accurate result than the modified Gram-Schmidt method when computing the QR decomposition of a matrix. Can ...
0
votes
2answers
40 views

How can I find $x$ such that $ax \equiv 1 \pmod{bx+c}$, given $a,b,c$?

Everything I've read about modular arithmetic generally concerns doing things in some "mod m" world where "m" is some constant. But I'm perplexed how to tackle modular arithmetic problems where the ...
1
vote
0answers
1k views

Change MATLAB code from Lax-Wendroff to Leapfrog

I want to see how leapfrog would look using this code, but I'm having issues implementing it. I think my biggest problem is adding in the $ U_j^{n-1}$ term, I just don't get the logic. Here's what ...
1
vote
1answer
36 views

Pumping lemma contradiction

I have to prove that the language $A_{1}= \{\alpha \in \Sigma^{*}|c^{a}(\alpha)>c^{b}(\alpha) \}$ where $\Sigma=\{a,b\}$, where $c^{a}(a)$ means the number of $a$ in $\alpha$, and $c^{b}(\alpha)$ ...
2
votes
2answers
110 views

Very slow convergence of a particular series?

I've read that $$ \sum_{k=2}^{\infty} \frac{1}{k (\log k)^2} = 2.1097\ldots $$ However when I compute the partial sums it looks like a lot of terms are needed to even get the first decimals right. My ...
1
vote
1answer
54 views

Computational complexity of expanding a MacLaurin/Taylor Series

What methods exist to computationally determine the first $k$ coefficients of a function (possibly polynomial or rational polynomial function)? How do Mathematica/MatLab/Maple/etc. solve this ...
2
votes
2answers
132 views

summation of ceil and floor function

I need a closed solution or a faster algorithm for calculating $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k}-1 \right\rceil $$ and $$ \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor $$ where $ ...
0
votes
2answers
477 views

Google Code Jam's Cookie Clicker Program…

Today, the Google Code Jam's cookie clicker problem was something like this. Problem In this problem, you start with 0 cookies. You gain cookies at a rate of 2 cookies per second, by ...
3
votes
1answer
88 views

Factors of integers of the form $k^2-k+1$

Factorisation of arbitrary integers is of course a computationally hard problem. But what if the integers I'm interested in factorising are all of the form $k^2-k+1$ ? Is there some way to compute ...
1
vote
0answers
38 views

Generating N-dimensional points acording to given distribution

I searched here on Math.SE and haven't found anything that was exactly what I was looking for, so I'm posting it here. If there is anything, pardon my ignorance. I thought it was my first post here, ...
1
vote
1answer
43 views

Please help with this Discrete fourier transform question

Consider the ODE $\frac {d^2u}{dx^2} + 2\pi\frac {du}{dx} + \frac 54\pi^2u = g(x)$ where g is a periodic fuction with period 1 given by $g(x) = e^{\pi x}$ , $ 0 \le x \lt 1$. It is desired to find ...
1
vote
1answer
34 views

Computational Maths - Normalised mantissa

What does overflow and underflow of an normalised mantissa mean?
1
vote
1answer
178 views

Max value - Mantissa calculation clarification?

I've been reading this article about floating point representation floating point representation is : Where mantissa is : All understood. But they also say : How did they get to ...
1
vote
1answer
136 views

Jacobi Iteration Question

I have a question that says use a relative tolerance of $10^{-3}$ and asks if the estimate errors are in line with the actual errors. What does relative tolerance mean and how do you work out ...
2
votes
1answer
260 views

Bisection Method Question, Multiple Roots

I understand how to do the bisection method and how to do it with a point of intersection. My question is should this not actually have multiple points of intersection? and if you're not given any ...
0
votes
1answer
60 views

Prove a language is Context Free

I am working on the following problem and I do make a little progress. Let me state the question first: Prove that the set of strings consisting of $a$'s and $b$'s with an equal number of $a$'s and ...
2
votes
0answers
40 views

Quantitatively comparing event trains of different lengths for Poissonness

I have a parameterized, effectively black box process that generates a series of events (simulated action potentials). Different parameter values often lead to different numbers of events. How can I ...
0
votes
1answer
36 views

Simple Error Question

I have a question which asks to find the absolute error and then asks if the actual error agrees with the theoretical error bound. Am I missing something or are absolute and actual error the same ...
3
votes
1answer
70 views

Computational Maths

I'm trying to revise for a test and these 2 questions I just don't really understand what I'm meant to do, any pointers would be good. Any help I'd be very grateful for.
1
vote
2answers
63 views

Knapsack variation NP-complete

I have C processors and $C$ items that have to be run on it. I can either run each item on a seperate processor and have a running time of $\sum_{i=1}^{c} c_i$, or divide the $C$ items into $k$ ...
0
votes
1answer
343 views

Computation Method to solving Homogeneous Fredholm Integral Equation of Second Kind with Symmetric Kernel

I am attempting to write a program that will be able to numerically solve a homogeneous Fredholm Integral Equation of Second Kind, with a Symmetric Kernel. I have been looking through textbooks and ...
3
votes
1answer
73 views

How do computers compute the expected value of an infinite distribution?

I was trying to compute: $$E[X] = \int^{\infty}_{-\infty} xP(x)dx$$ but it might be a distribution over a sample space that is infinite. How do computers actually deal with this in an efficient and ...
0
votes
1answer
158 views

Newton Cotes Rule Derivation

I have this question Derive an open two-point Newton-Cotes quadrature rule for the interval $[a,b]$. I need to find what the resulting weights and nodes are. What is the degree of the resulting rule? ...
1
vote
2answers
81 views

Computing an induced matrix norm

Assume I have a $n \times n$ matrix and a norm defined as $\|A\| = \max \limits_{x \not = 0}\frac{\|Ax\|}{\|x\|}$, where $\|x\| = \sqrt{\sum x_i^2}$. How can I compute this norm?
2
votes
1answer
123 views

No advantage to the closed form for Fibonacci numbers?

The closed forms for the Fibonacci sequence, such as: $$F_n=\frac{\varphi^n-\widehat\varphi^n}{\sqrt5}=\frac{\varphi^n}{\sqrt5}-\frac{\widehat\varphi^n}{\sqrt5}\;,$$ the Binet formula, do not seem ...
13
votes
2answers
224 views

$e$ popping up in topic I'm unfamiliar with

I programmed up a little algorithm that goes like this: Fix two positive, real numbers, call them $\alpha$ and $\beta$. Generate a new, random, real number, $x \in [0,1]$ Set $\alpha$ = ...
5
votes
2answers
861 views

“Opposite” of idempotent operation?

What is the adjective given to a mathematical operation/expression on a variable whose new value can only be described in terms of that variable's existing value? Sequential operation? Example: i = ...