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

45
votes
4answers
3k views

Is “A New Kind of Science” a new kind of science?

A couple of years ago I was reading "New Kind of Science" (NKS) by S. Wolfram, and it presented lot of interesting ideas for a young Physics undergraduate. Now that I am studying Mathematics however, ...
28
votes
3answers
10k views

What algorithm is used by computers to calculate logarithms?

I would like to know how are logarithms calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
23
votes
1answer
496 views

Computing (on a computer) the first few (non-trivial) zeros of the zeta function of a number field

If $K$ is a number field, whose Galois closure over the rationals has degree 24 or so, and whose discriminant is around $163^4$, then what is a numerically efficient way of computing the first few ...
20
votes
8answers
3k views

Rapid approximation of $\tanh(x)$

This is kind of a signal processing/programming/mathematics crossover question. At the moment it seems more math-related to me, but if the moderators feel it belongs elsewhere please feel free to ...
17
votes
5answers
913 views

What interesting open mathematical problems could be solved if we could perform a “supertask” and what couldn't?

If we had a computer that could perform a countably infinite number of steps of a Turing machine, what currently open problems could we solve? I guess a lot of number theory problems could be solved ...
14
votes
1answer
2k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
13
votes
2answers
217 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$ = ...
12
votes
1answer
689 views

Why are there mathematicians that do not use computers?

I was watching a video on Andrew Wiles and his proof of Fermat's Last Theorem and I quite liked the video, especially the complexity of the proof only to prove a simple concept which can be understood ...
12
votes
1answer
165 views

Evaluation of a slow continued fraction

Puzzle question... I know how to solve it, and will post my solution if needed; but those who wish may participate in the spirit of coming up with elegant solutions rather than trying to teach me how ...
12
votes
1answer
314 views

Krylov-like method for solving systems of polynomials?

To iteratively solve large linear systems, many current state-of-the-art methods work by finding approximate solutions in successively larger (Krylov) subspaces. Are there similar iterative methods ...
11
votes
1answer
365 views

Constructing a finite field

I'm looking for constructive ways to obtain finite fields, for any given size $q=p^n$. For example, I know it suffices to find an irreducible polynomial of degree $n$ over $\mathbb{Z}_p$ (and then ...
10
votes
1answer
710 views

How else can we be nauty?

The graph canonical labelling package nauty is widely regarded as one of the best (if not the best) around. Unfortunately, it's quite a large package, and making a GPU version seems to be a highly ...
10
votes
2answers
898 views

How do I prove the partial denominators formula of the Bauer-Muir transformation of a generalized continued fraction?

Notation: $b_{0}+\underset{n=1}{\overset{\infty }{\mathbb{K}}}\left( a_{n}/b_{n}\right) $ is the Gauss Notation for generalized continued fractions. Description of the Bauer-Muir transformation ...
10
votes
0answers
98 views

Product of primes mod n

Let $n$ be an odd composite number. I'm trying to compute $$ f(n)=\prod_{n/2<p<n}p\pmod n $$ where $p$ ranges over the primes in the indicated region. Can this be done (significantly) faster ...
9
votes
2answers
234 views

Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$

I realize there is probably not a closed form, but is there an efficient way to calculate the following expression? $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$ I've noticed $$\sum_{k=1}^n ...
9
votes
2answers
2k views

How to check whether an ideal is a prime (or maximal) ideal?

I have a ring $R$ which is known to be a Dedekind domain, but not necessarily a Euclidian domain, and a nonzero ideal generated by one or two elements in this ring. How can I check if this ideal is a ...
9
votes
2answers
433 views

Computing the “lying over”, “going up”, “going down” ideals.

For any commutative unital ring $R$ and an ideal $\mathfrak{a}$ of $R$, we shall denote $$\begin{align*} \mathrm{Spec}(R)&:=\{\text{prime ideals of }R\},\\ ...
8
votes
4answers
816 views

What is the most efficient way to calculate the sine of a rational number?

I'm happy that we can use some trig identities like $$\sin\left(\frac{\theta}{2}\right) \equiv \pm \sqrt{\frac{1-\cos(\theta)}{2}}$$ and $$\sin(\alpha \pm\beta) \equiv \sin(\alpha) \cos(\beta)\pm ...
7
votes
9answers
8k views

Fastest Square Root Algorithm

What is the fastest algorithm for finding the square root of a number? I created one that can find the square root of "987654321" to 16 decimal places in just 20 iterations (I'm not ready to release ...
7
votes
1answer
380 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 ...
7
votes
1answer
151 views

Fractional part of exp(x)

I have a real number $x$ (for concreteness, say $10^4<x<10^6$) and would like to find $e^x-\lfloor e^x\rfloor$ to reasonable precision (10-20 decimal places). What is the most efficient method? ...
6
votes
2answers
155 views

How was the $3x+1$ problem checked up to $5 \times 2^{60}$?

The Wikipedia article for the Collatz conjecture states that: The conjecture has been checked by computer for all starting values up to $5 \times 2^{60} \approx 5.764 \times 10^{18}$. It gives ...
6
votes
3answers
235 views

Mathematical Limitations of Computer Experiments

One problem that has always bothered me is the limitations of computers in studying math. With a chaotic dynamical system, for example, we know mathematically that they possess trajectories that never ...
6
votes
2answers
2k views

Fast Matlab Code for hypergeometric function $_2F_1$

I am looking for a good numerical algorithm to evaluate the hypergeometric function $_2F_1$ in Matlab (hypergeom in Matlab is very slow). I looked across the ...
6
votes
2answers
460 views

Accelerating Convergence of a Sequence

Suppose I had a monotonically increasing sequence $\{d_{n}\}$ which is also bounded above. The $d_{n}$'s satisfy a given recurrence, however computationally they tend very slowly to the limit. What ...
6
votes
1answer
584 views

How to find an expression whose value is 190

Given a set of numbers (in this case): 3, 7, 7, 100, 50 Either: prove it is impossible to form the number k = 190 using ( ) + - * / operators between sub set of the these numbers ex: 1000 = ((3 + ...
6
votes
1answer
200 views

how to calculate this complementary Bessel function?

I am trying to calculate this complementary Bessel function $$\Psi(a,b,\gamma)=\int_0^\infty\Phi({a\over \sqrt{u}}+b\sqrt{u}){u^{\gamma-1}e^{-u}\over \Gamma(\gamma)}du$$ where $\Phi$ is the standard ...
6
votes
2answers
197 views

What is the average weight of a minimal spanning tree of $n$ randomly selected points in the unit cube?

Suppose we pick $n$ random points in the unit cube in $\mathbb{R}_3$, $p_1=\left(x_1,y_1,z_1\right),$ $p_2=\left(x_2,y_2,z_2\right),$ etc. (So, $x_i,y_i,z_i$ are $3n$ uniformly distributed random ...
5
votes
1answer
1k views

A search for integers which can be written as a sum of two squares in multiple ways

As part of a number theory hobby project, I'm looking for a computational way to enumerate all integers $n$ which can be written as a sum of two integer squares in three or more ways. The range of ...
5
votes
1answer
154 views

What's the best way to detect an algebraic number?

Suppose you calculate the first few (dozen, hundred) digits of a number which you believe to be a rational number. You can calculate the continued fraction for the number and truncate after a large ...
5
votes
3answers
412 views

FFT with powers of 3

Classic Fast Fourier Transfrom (FFT) works fine, when $n$ is power of 2. How to generalize FFT procedure when $n$ is power of 3? Is it possible to easily modify the algorithm and preserve its ...
5
votes
3answers
794 views

What free software can I use to solve a system of linear equations containing an unknown?

Question: What free software can I use to solve a system of linear equations $M\mathbf{x}=\mathbf{y}$ where the entries of $\mathbf{y}$ vary with an unknown quantity $n$? Presumably I could do ...
5
votes
1answer
2k views

How does Knuth's algorithm for calculating logarithm work?

I had a look at Knuth's The Art of Computer Programming, book 1. In chapter 1, section 1.2.2, exercise 25, he presents the following algorithm for calculating logarithm: given $x\in[1,2)$, do the ...
5
votes
2answers
292 views

Abuse of big-O notation? (version 2 - simplified and revised)

Given exam question: Algorithms A & B have complexity functions $f(n)=2 log(n^3)+3n$ and $g(n)=1+0.1n^2$ respectively. By classifying each $f$ and $g$ as $\mathcal{O}(F)$ for a suitable ...
5
votes
3answers
521 views

Calculate $\pi$ in an arbitrary base, to arbitrary precision

I need to calculate $\pi$ -- in base: 4, 12, 32, and 128 -- to an arbitrary number of digits. (It's for an artist friend). I remember Taylor series and I've found miscellaneous "BBP" formulas, but so ...
5
votes
1answer
155 views

Efficient free alternative to *Mathematica*

I am searching for a free alternative to Mathematica. By efficient, I mean that it should have every (or at least almost every) function that you can find in Mathematica, including for example Number ...
5
votes
0answers
62 views

A summation involving the ceiling function

I'm trying to find a better method of calculating the sum $$\sum_{k=1}^N\lceil ak\rceil^2$$ where $a$ is an irrational number. So far, my only idea is to somehow use a best rational approximation. ...
5
votes
0answers
171 views

A property of the subgroups lattices

Let $G$ be a finite group. Consider all the subgroups $H$ such that its subgroups lattice $\mathcal{L}(H)$ is distributive (i.e. the group $H$ is cyclic, by Ore's theorem), and among them, let $\{ ...
5
votes
1answer
432 views

Cylinder-ray intersections equation

I found an article involving infinite cylinder-ray intersections, and I don't know how they develop this equation: $$(q - p_a - (v_a, q - p_a)v_a)^2 - r^2 = 0$$ In the end of the first page I quote: ...
4
votes
4answers
357 views

Computing partition numbers

Today a friend and myself came up with the question of computing partitions of numbers, i.e.: given a number $n$, what is the number $p(n)$ of was of different ways writing $n$ as a sum of non-zero ...
4
votes
1answer
65 views

GAP code to get Multiplication Table.

I have a finite set $S=\{0,1,2,\ldots,n-1\}$ and binary operation $\star$ on $S$ defined by $$x\star y= \left\{ \begin{array}{l l l} \frac{3(x+y)}{2} ~~\text{modulo} ~~n& \qquad \mbox{if $x$ ...
4
votes
2answers
268 views

The J programming language: is it useful for mathematics?

I just stumbled upon the J programming language, which has the description: J is particularly strong in the mathematical, statistical, and logical analysis of data. It is a powerful tool in ...
4
votes
2answers
469 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 = ...
4
votes
1answer
56 views

About parallel time computation

I am studying a paper where it is mentioned that Newton iteration may be used to compute the inverse of $n \times n$, well- conditioned matrix in parallel time $o(\log^2n)$ and that this computation ...
4
votes
1answer
159 views

Hilbert curve scheduling not theoretically well defined?

In high-dimensional task scheduling, it is common to use a Hilbert-curve ordering. Given a set of points $\{p_i\}_{i=1}^N \subset \mathbb{R}^d$ the goal is to linearly order them such that points ...
4
votes
1answer
316 views

Computing with ideals: over $K$ or over $\mathbb{Q}\subseteq K$? does it matter?

I'm beginning to learn to use SINGULAR, the computer algebra system (CAS) for commutative algebra. NOTATION: If $K$ is a field of characteristic $0$, then $\mathbb{Q}\subseteq K$; otherwise ...
4
votes
1answer
64 views

Defining a subgroup of $GL(2,7)$ in GAP

Considering this resent post in which $|G|=42$, I am thinking of making this subgroup concrete in GAP environment. Maybe, if the structure of $G$ was known then, we would use an appropriate mapping ...
4
votes
1answer
144 views

What is the upper bound on the error of a matrix multiplication

When both A and B are n x n upper-triangular matrices, the entries of C = AB are defined as follows: $$ c_{ij} = \begin{cases} \sum _{k=i}^ja_{ik}b_{kj} & 1\leq i\leq j\leq n \\0 & 1\leq j\lt ...
4
votes
1answer
76 views

Need little hint to prove a theorem from a paper

I have an iterative method \begin{eqnarray} X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots \end{eqnarray} with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
4
votes
5answers
84 views

A equation of Trigonometry

hello dear friends please help me to solve this problem.Thanks very much. How much are $a$ and $b$ in the problem below? $$1-2\cos 3a +2\cos 3b=0$$$$1-2\cos 5a +2\cos 5b=0$$