text:
An amazing new set of conjectures and the jacobian conjecture

<NAME> is one of the world experts on the Jacobian Conjecture. He has written a book on the problem—really the book. Besides this he has made many contributions to the understanding of this great conjecture.

Today I plan to talk about a paper Essen just put into the archives on the Jacobian Conjecture (JC). His paper is amazing—really amazing. Its title is The Amazing Image Conjecture.

Years ago Essen, <NAME>, and I wrote a simple paper on an approach to the JC. The paper is I still believe a viable approach to the problem. But we could only prove a very weak result about the JC problem.

Since we could not make our ideas work, lets turn to Essen’s new paper.

Jacobian Conjecture

I thought you might like to go through a possible scenario of how the JC was created, and see some of the rationale behind the conjecture. This is not a “real” history, but one that I hope helps expose the ideas that go into the creation of a great conjecture.

Imagine that you are studying mappings ${F}$ from the two dimensional Euclidean plane to itself. A natural question is: when is ${F}$ one-to-one? There are many properties that mappings may or may not have, but being one-to-one is a basic property. Such functions are called injective—this name is due to Nicolas Bourbaki.

The first thing you notice is that ${F}$ being injective is a “global” property, since ${F}$ is one-to-one, or injective, provided there are no two distinct points ${a}$ and ${b}$ in the plane so that

$\displaystyle F(a) = F(b).$

Determining whether or not there are such distinct points is equivalent to asking for the solvability to the two equations

$\displaystyle \begin{array}{rcl} f(a_1,a_2) &=& f(b_1,b_2) \\ g(a_1,a_2) &=& g(b_1,b_2) \end{array}$

where ${(a_1,a_2) \neq (b_1,b_2)}$ and ${F(x,y) = (f(x,y),g(x,y))}$.

In general deciding whether such equations have a solution can be very difficult. In order to have any hope of solving this problem you decide to restrict the function ${F}$ to be a polynomial mapping: this means that ${f(x,y)}$ and ${g(x,y)}$ are both polynomials.

Even with the restriction to polynomial maps the difficulty is that ${a}$ and ${b}$ can be anywhere in the plane; they need not be “near” each other. This global nature is the key reason that determining whether or not ${F}$ is injective is hard.

You realize one way to simplify the problem is to ask a much weaker question: is the mapping ${F}$ “locally injective?” The mapping ${F}$ is locally injective if for each point ${p}$ there a disk around ${p}$ so that for all ${a}$ and ${b}$ in the disk if ${F(a) = F(b)}$, then ${a=b}$.

There are two reasons you think this is a good move. First, the mapping ${F}$ cannot be injective unless it is locally injective at every point ${p}$. This is a simple idea, but a powerful one. When facing a tough question, often relaxing the question can yield insight.

Second, you recall a classic theorem that has a sufficient condition for a smooth map to be locally injective at a point. The theorem is the famous Inverse Function Theorem. In one dimension it says that a function ${h}$ is locally injective at point ${p}$, provided

$\displaystyle f'(p) \neq 0.$

For example, ${h(x) = x^2}$ is locally injective at any point ${p \neq 0}$.

The Inverse Function Theorem generalizes this simple idea from calculus-101 to two dimensions and beyond. The critical question is what takes the role of the derivative of a function? It turns out the role is played by the Jacobian matrix of the mapping ${F}$—clearly we are close to why the conjecture is called the JC.

Associated with any mapping smooth ${F}$ is the Jacobian matrix defined as

$\displaystyle J_F(x,y) = \left[ {\begin{array}{cc} f_x(x,y) & f_y(x,y) \\ g_x(x,y) & g_y(x,y) \\ \end{array} } \right]$

Note, ${f_x(x,y)}$ is the partial derivative of the function ${f}$. In the one dimension case this would degenerate to the ${1}$ by ${1}$ matrix of ${f_x(x) = f'(x)}$. If the determinant of this matrix is non-zero at the point ${p}$, then by the famous inverse function theorem the map ${F}$ is locally injective at ${p}$.

Thus to tell if the mapping ${F}$ is locally injective at every point you need only look at the determinant of the matrix ${J_F(x,y)}$. Note this is a polynomial in the variables ${x}$ and ${y}$. It can be a high degree polynomial, and over the reals it could be quite difficult to tell if this polynomial is or is not ever ${0}$. For example, does

$\displaystyle 17x^3 - 348xy^6 + x^7 - 89x^2y^4 + 12 = 0$

have a solution over the reals?

Now you make a move that is brilliant. Rather than try to figure out whether such polynomials have zeroes or not you realize that the polynomial ${c}$ where ${c}$ is a non-zero constant has no zeroes. So you make the `simplifying” conjecture:

Conjecture: If ${F}$ has ${ \det(J_F(x,y)) = c }$ where ${c}$ is a non-zero constant, then ${F}$ is globally injective.

This is the Jacobian Conjecture due to Ott-Heinrich Keller in 1939, and later <NAME> gave it the modern name.

You might ask why not replace the condition ${ \det(J_F(x,y)) }$ is a non-zero constant by the condition ${ \det(J_F(x,y)) }$ is never zero for any real numbers. The answer is surprising—it is false. This was the so called “Real Jacobian Conjecture,” which is now known to be false. See this for a counter-example due to <NAME>.

I will not go into more details, but the intuition I believe is that many real analysis problems are only understood when complex numbers are allowed. This happens in understanding the singularities of rational functions. For example the reason the power series of ${ 1/(1+x^2)}$ has radius of convergence only ${1}$ is there is a complex singularity. In the reals this function has no poles, while over the complex numbers it has a pole at ${i}$.

JC Approaches

There have been many claims of proofs of JC, some are still active claims. The incorrect proofs of JC—I think all have been proofs not counter-examples—have been by amateurs and professionals alike. The problem is slippery. There seems to be many difficulties in understanding the problem. Yet the problem’s statement only requires basic calculus.

JC seems to be one of those problems that should be resolvable. Yet so far it has withstood the attacks of mathematicians for over 70 years. Since then there have been many partial results and reductions, but no proof yet.

${\bullet }$ Equivalent Problems: Like many problems in mathematics there are numerous equivalent statements. See Essen’s book for many examples. One of the most famous is to reduce the degree of mapping ${F}$. In order to do this the problem is generalized to higher dimensions: the map ${F}$ is allowed to be

$\displaystyle F(x) = (f_1(x),\dots,f_n(x))$

where ${x = (x_1,\dots,x_n)}$. <NAME>, <NAME>, and <NAME> proved the famous:

Theorem: If the generalized JC is true for all ${n}$ and polynomial maps of degree at most three, then JC is true.

As often is the case, two is special. The general JC is easily proved for mappings of degree at most two.

${\bullet }$ Direct Proofs Attempts: One “obvious” idea is to try and prove an inductive statement. If ${F = (f,g)}$ is the mapping, then prove that there is a transformation of ${F}$ that preserves injectivity and lowers the degree. A claim a few years ago was based roughly on this type of approach, but it fell apart.

${\bullet }$ Advanced Attempts: There were approaches to the JC problem based on advanced ideas of algebra. I am the last one to discuss these, but while they look possible they have not yet worked.

${\bullet }$ Algebra or Analysis: There are other approaches based on analysis rather than algebra. Of course all methods are allowed, but I have often thought the problem is closer to number theory than algebra, again who knows.

Amazing Conjectures

Essen’s amazing paper describes a beautiful connection recently discovered by <NAME> between the JC and some striking questions that seem interesting on their own. There are a new set of extremely interesting conjectures. I will explain one of them—see Essen’s well written paper for the full set of conjectures.

The generic class of open problems concern particular linear functionals ${L}$ on spaces of polynomials. Call ${L}$ “nice” if the only polynomial ${f}$ such that ${L(f^m) = 0}$ for all ${m \ge 1}$ is the zero polynomial. The amazing fact is that there exist particular functionals ${L}$ such that: if ${L}$ is nice, then JC is true. These functionals are still fairly complicated to define, so here I will follow Essen’s paper by starting with three simpler functionals for which niceness is non-trivial—and still open for the third:

$\displaystyle \begin{array}{rcl} A(f) &=& \int_0^1 f(x) dx \\ B(f) &=& \int_0^{\infty} f(x)e^{-x} dx \\ C(f) &=& \int_0^{\infty} \cdots \int_0^{\infty} f(x_1, \ldots, x_n) e^{-(x_1 + \cdots + x_n)} dx_1 \ldots dx_n \end{array}$

Each of ${A,B,C}$ sends a polynomial to a scalar. The questions are:

1. If ${A(f^m) = 0}$ for all integers ${m \ge 1}$, must ${f=0}$?
2. If ${B(f^m) = 0}$ for all integers ${m \ge 1}$, must ${f=0}$?
3. If ${C(f^m) = 0}$ for all integers ${m \ge 1}$, must ${f=0}$?

Essen can prove the first two are true for univariate polynomials, but the third about ${C(f^m) = 0}$ is open for multi-variate polynomials.

I will give a bit of flavor of how he proves such theorems, but as always see his paper for the details.

Consider the polynomial

$\displaystyle f(x) = c_n x^n + \cdots + c_l x^l$

where ${l>0}$ and each coefficient is a Gaussian integer. I am assuming that the constant term is zero, and plan on showing the lowest term is also zero. This will inductively prove that ${f}$ is zero.

The key is to raise the polynomial to a special power ${m}$, which is selected so all the terms but the last “disappear” when ${B}$ is applied. Let ${m = (p-1)/l}$ where ${p}$ is a prime and ${l}$ divides ${p-1}$. Then, ${f^m}$ is congruent to

$\displaystyle g(x) = h(x) + c_{l}^m x^{ml}$

modulo ${p}$. Define ${d}$ to be the minimum degree of the terms of ${h(x)}$. Then ${d}$ is at least

$\displaystyle lm + 1 = p.$

Thus ${B(f^m)}$ is congruent modulo ${p}$ to

$\displaystyle c_{l}^m (p-1)!,$

since all the terms in ${h(x)}$ have degree at least ${p}$. It is easy to prove that ${B}$ maps

$\displaystyle x^r \rightarrow r!.$

It follows that ${c_{l}^m}$ is divisible by ${p}$, and that ${c_l = 0}$. The latter uses that ${c_l}$ is a Gaussian integer.

Open Problems

Of course the open question is the JC. Is it true? This problem is not a Clay problem—perhaps it should be added to replace the Poincaré, Conjecture. The problem JC is on Steve Smale’s list of open problems as problem ${17}$.

1. July 18, 2010 6:19 am

i don’t understand the finite field case.
if a polynomial map: GF(2)^n -> GF(2)^n has non-invertible jacobian matrix, does this mean the map is not one-to-one? (the derivative is the formal derivative in case this makes any sense…)

July 18, 2010 3:24 pm

j,

Do not get your question. The JC is over the complex numbers. However, it makes sense over any field and even over commutative rings. Check out Essen book where he discusses some issues related to finite fields.

• July 20, 2010 9:46 am

{x-y, 3x+3y} over Z/24Z ?

• August 29, 2010 7:33 am

sorry my question wasn’t clear, will try to explain by example:

given a polynomial map GF(2)^n -> GF(2)^n can you probabilistically tell if it is one-to-one?

a specific example: consider the md5 hash function restricted to 128 bit input (16 bytes). the output is 128 bits too and it is a map GF(2)^128 -> GF(2)^128. (addition mod 32 can be emulated over GF(2) basically by using an adder circuit).

i was told it is open question if this is one-to-one.

a possible approach of settling this may be to try to use the jacobian matrix.
to compute the numerical jac. matrix partial derivatives can be computed via automatic differentiation (http://en.wikipedia.org/wiki/Automatic_differentiation taking into account x^k = x, k>0) or Derivatives of Binary Functions (http://cr.yp.to/cubeattacks.html see the scanned pages by djb).

so if the jacobian matrix has determinant 0 on random input it is not invertible (if it is 1 it is possible just to be the value of polynomial). i got a 0 witness for 128 bit md5 and failed to get 0 witness for the known 1-to-1 128 md5 restricted to the 1st round.

do you have opinion if md5 restricted to 128 input is one-to-one ?

2. July 18, 2010 12:51 pm

Thanks so much for sharing this fantastic conjecture. I’m shocked that the general real case has a counter-example.

July 18, 2010 9:56 pm

This is a great problem.
I read the wikipedia article on the
Jacobian conjecture first.

I wonder why the wikipedia definition
of the conjecture defines the mappings
to be between complex numbers rather
than from the two dimensional Euclidean
plane to itself.

In this definition it’s obvious why the
Jacobideterminant has to be a constant.
But how can it still be the same conjecture?

July 19, 2010 8:12 am

I thought real case would be more natural. The problem makes sense over any field or even ring. So there are many versions—which are often the same, We this, of course, all the time in theory. For example, if can prove over the rationals or even integers that implies JC—need to allow any number of variables.

July 19, 2010 4:27 pm

I absolutley agree that the real case is much more natural.
even i can see why this is an interesting problem :-)

I guess i just got confused, that over the complex numbers
it’s much easier to show the Jacobideterminant has to be a
constant. But as <NAME>s counterexample is known
in the real case, you don’t have an advantage for the real case
anymore.

Am i right in thinking if the counterexample of Pinchuk
wouldn’t been known, the real case looks easier to proof
than the complex case?

If i am right i would have another question, i’m sorry if this is a
stupid question as i’m actually less than an amateur:

As the problem makes sense over any field or even ring, is
it proven over any field or ring, that the jacobimatrix has
to be a constant?

July 19, 2010 2:27 pm

Over an algebraically-closed field like the complex numbers, a (possibly multivariate) polynomial is a nonzero constant if and only if it is nowhere zero.

July 19, 2010 2:48 pm

I wonder – are there proofs in complexity theory that draws upon the world of complex numbers ?

Quantum world – yes. but in classical or probabilistic cases?

July 19, 2010 5:48 pm

Mendel,

Yes the real case looked nice—I would think. The reals have ordering and other properties that might have been exploited.

Your last question is quite interesting. Must the det be constant over other fields? I think likely to be yes for some other fields, but I do not know the answer.

7. July 20, 2010 6:43 am

Hmmm … Dick’s column gives a name to a problem that arises naturally in quantum simulation theory, that problem being: Given a (finite-dimensional) Hilbert vector that can be written as a tensor network state of rank r, is the tensor network representation unique?

We can regard the tensor network state as a compressed algebraic representation of the Hilbert vector, so the question is really about the uniqueness of algorithmically compressed quantum states. We see that it is also natural to restrict the question to bosonic (symmetrized) and fermionic (antisymmetrized) tensor network states.

It is perfectly feasible to search numerically for tensor network representations, and these searches turn out to work amazingly well, in essence because the manifold of tensor network has both a ruled structure and negative sectional curvature.

Our impression from numerical experiments is that the uniqueness conjecture is true for tensor network states, but on the other hand, it never occurred to us to search for counterexamples. For that idea, we are indebted to Dick’s fine post!

Often-times it’s not easy to recognize the correspondence between abstract mathematical theorems and practical engineering problems, so comments regarding the relevance of existing theorems to the injectivity of tensor network maps would be welcome.


text:
## The nature of mathematics

Posted in Uncategorized on January 31, 2010 by quantummoxie

One particularly contentious question in the foundations of both mathematics and physics is whether mathematics is discovered or invented. Related to this is whether mathematics is the way the world actually is or if it is simply a way in which we can model the world.

This is a particularly difficult question to answer since it is quite clear that there are physically impossible situations that can be spoken about in mathematics. The best example I can think of relates directly to some things I bitched about on this blog in recent weeks concerning Brikhoff’s theorem (which I won’t rehash in the interest of brevity): taking n copies of a quantum channel should start to approach something that can be approximated by unitaries as n approaches infinity, i.e. in the asymptotic limit, n copies of a channel have a unitary representation (roughly speaking and if the theorem is correct). But, from a physical point of view, this is ridiculous since it is literally impossible for an infinite number of channels (or anything else, for that matter) to physically exist. Yet whole branches of mathematics are devoted to working with infinity (infinite sets, for example).

Clearly some mathematical results have been originally thought to be entirely abstract only to much later find some application in the physical world. But it could be argued that concrete, mathematical analyses of infinite things could never, by their very definition, find an application in the physical world. Does this mean that mathematics is inherently discovered then? Or could it be taken as “evidence” for the Many-Worlds Interpretation (MWI), i.e. the only way to have a physically infinite result is to have a physically infinite number of universes?

## Wow, this is cool

Posted in Uncategorized on January 29, 2010 by quantummoxie

I just stumbled across this thanks to the responses to my previous post: Math Overflow. I am now a registered user and they have a quantum mechanics tag! 🙂

## A quirky mathematical problem in need of explanation

Posted in Uncategorized on January 28, 2010 by quantummoxie

In my travails with the QIP Program Committee, one argument that went back-and-forth was whether or not the so-called Gell-Mann matrices (one possible representation of generators of SU(3)), when used as Kraus operators for a quantum channel, are extremal (we’re only concerned with extremality here, and not unitality). Landau and Streeter proved that a set of Kraus operators, $A_{i}$, is extremal if and only if the set

$\{A_{k}^{\dag}A_{l}\}_{k,l \ldots N}$

are linearly independent. I argued they were and Michael Ben-Or argued they were not. Oddly it appears we are somehow both correct (which only means there’s something else going on here that one or both of us missed). So I present here our two arguments and solicit your comments on this mathematical quandary.

Argument 1: They are extremal
I proved this in a straightforward way – I used Mathematica. I tried it several ways, but just to be sure I solicited suggestions in my previous blog post on how to tell Mathematica to check exactly what Landau and Streeter proposed. The result indicates that they are, indeed, linearly independent. Click here to see a PDF file export of the Mathematica notebook that includes both the input and the output (I don’t have a premium WordPress account so I can’t upload the actual notebook, but you can copy and paste from this into Mathematica if you want to tweak it yourself).

Argument 2: They are not extremal
Michael’s approach was to show that the channel constructed with the Gell-Mann matrices as Kraus operators are a convex combination of three other channels and thus can’t be extremal. He also crunched his numbers with Mathematica and here is a link to the PDF file of his notebook.

In my estimation, if Michael is correct and I didn’t make any errors in translating things to Mathematica then there’s something wrong with Landau and Streeter’s criterion for extremality. If anyone has any thoughts on this, I am eager to hear them.

## Stumped by Mathematica – anyone?

Posted in Uncategorized on January 26, 2010 by quantummoxie

I need to determine if a large set of matrices are linearly independent, i.e. linearly independent from each other (not linearly independent in their individual rows and columns). Anyone have any ideas on how to efficiently do this in Mathematica?

## QIP – Final Post (Thursday & Friday recap)

Posted in Uncategorized on January 23, 2010 by quantummoxie

Well, I’ve been so busy with the conference and squeezing a bit of sight-seeing that I am only now getting around to posting the recaps of Thursday and Friday. I would say that my first QIP has been a major success for me personally as I learned an awful lot, including the very important differences between physicists and computer scientists. I have a much better appreciation for how the quantum information community as a whole operates, despite my many years working with APS GQI. Anyway, on to the talks.

Thursday morning’s session began with an awesome talk by <NAME> (see arxiv.org:0811.3171v3) on work he performed with <NAME> and <NAME> on developing a quantum algorithm for solving linear systems of equations. Now this is something just about anyone with an undergraduate background in engineering, math, physics, computer science, maybe even chemistry or even economics could wrap their head around. Solving linear systems of equations – linear algebra – is one of the most widely used bits of mathematics. For instance, it’s the basis of finite element analysis which forms the backbone of structural engineering. In any case, the idea is to solve the equation $A\bar{x}=\bar{b}$ (by the way, I highly recommend watching the video if you can, since many of his early slides were hilarious). Here we’re assuming that A is an $N \times N$ matrix. If A happens to not be Hermitian, then we have

$\left(\begin{array}{cc} 0 & A \\ A^{\dag} & 0\end{array}\right)\cdot\left(\begin{array}{c}0 \\ \bar{x}\end{array}\right) = \left(\begin{array}{c} \bar{b} \\ 0 \end{array}\right)$.

Of course there are an endless number of classical algorithms out there to solve these types of things (just think back to your linear algebra class or google it). Essentially the goal, of course, is to invert A in order to find x. The efficiency of these algorithms can be compared via their condition number $\kappa$. So, the quantum algorithm is roughly as follows:

$|b\rangle = \sum_{i}^{N} b_{i} |i\rangle$ is a unit vector. Suppose A is a sparse and that $\kappa^{-1} \le |A| \le I$. Then we have

$|x^{\prime}\rangle = A^{-1}|b\rangle$ where $|x\rangle = \frac{|x^{\prime}\rangle}{|\sqrt{\langle x^{\prime}|x^{\prime}\rangle}}$.

What this algorithm produces is $|x\rangle$ and $\langle x^{\prime}|x^{\prime}\rangle up to some error,$latex \epsilon\$ in a much better run-time than classical algorithms. Specifically, its run time is $\mathcal{O}(\kappa t_{B} + \textrm{log}Ns^{2}\kappa^{2}/\epsilon)$ compared to $\mathcal{O}(\textrm{min}N^{2.376},Ns\sqrt{\kappa},(s/\epsilon)^{\mathcal{O}(\sqrt{\kappa})}, \textrm{etc.})$ (assuming I’m reading my notes correctly).

The advantages of this method come from the relatively small $\kappa$ and the sparseness of A. The run-time really can’t be improved by much and so this is pretty much the limit on the optimality of the problem (from what I gathered anyway). The algorithm is based on two key primitives that are what invert the action of A: Hamiltonian simulation and phase estimation. Doing so coherently gives either a $|0\rangle$ (destruction) or $|1\rangle$ result. The best lower bound on the run-time with this method is $\sqrt{\kappa}$.

Now, comparing this to finite element models, this quantum algorithm can apparently be tweaked to be a bit better than the best finite element models out there, e.g. it can solve thermal conductivity in 36 spatial dimensions. Actually, there are in fact several types of solutions for the quantum algorithm that can be used to compare to Monte Carlo methods. Now, interestingly enough if the run-time could be improved to $\kappa^{\frac{1-\delta}{2}} \cdot \textrm{poly log}N$, it would apparently imply that BQP = PSPACE, though I’ll readily admit I’m not entirely sure I understand why (but I trust they know what they’re talking about). In addition the algorithm also apparently proves BQP-hardness, though again, I’m not sure I understand the details.

One thing they’re looking for is more applications. Luckily, I used to be a mechanical engineer who worked on fluid mechanics. I may have some possibly wicked hard real-world problems that might be a good test for them. For instance, one interesting question Aram suggested is how costly would it be to high-energy theory with low-energy states? Anyway, on to the next few talks, but congrats to Aram on an excellent talk – probably my favorite from the workshop.

<NAME> went next and gave a talk about self-correcting quantum memories in conjunction with a bath that is supposed to improve on the Kitaev model. The connection to the bath was in the weak coupling limit. Further details on this work can be found at arxiv.org:0908.4264. The next talk was by <NAME> on quantum computation on Turaev-Viro codes. It was basically cool topological stuff – lots of neat topological diagrams including one I’m calling the upside-down pants diagram. Their paper didn’t have a picture of it, but let’s just put it this way: <NAME>, who was sitting next to me, noted that it seemed to indicate that crossing one’s legs (which I was doing at the time) is like performing a unitary transformation on a pair of pants (hey, I’m a talented guy). Anyway, there was a lot of cool category and graph theory stuff and it’s a really neat approach to coding. I can’t say I understood every last detail, but it was a cool talk nevertheless.

<NAME> following that with some more topology/graph theory stuff relating to stabilizer codes. Basically it was about trying to enable universal quantum computation (UQC) or, put another way, how close to that ideal can we get? How much of the quantum computing “power” can we obtain? His work uses a Clifford polytrope with a nifty octahedron lattice (while the geek in me should have been thinking it looked like D&D dice, I’ve been playing Zome Tools recently and kept thinking it looked like something I had built with them). One of his results was that UQC for single-qubit gates reduces to UQC for single-qubit states. Given a noisy operation that violates something, for example, his approach can tell you which measurement to perform. At the moment he’s only tackled unital noise, but non-unital would be useful.

<NAME> went next with a simple approach to approximate quantum error correction (AQEC). Prior work has mostly been on perfectly-correcting the CP noise channel asking how far a proportionality factor, $\varepsilon$, is from trace-preserving (in fact she later defined “perfect” QEC). So what is AQEC exactly? It’s a smaller system that’s used to encode the information while not sacrificing much reliance against noise. You could think about AQEC as an optimization problem. Semi-definite programming methods are one example, though it gives an average performance. What she was interested in was the absolute worst-case performance scenario so that she could come up with something that worked for all channels. What AQEC does is condition perturbation conditions by tossing in an extra factor to the channel. So, for example, take a look at this:

$PE_{i}^{\dag}\varepsilon (P)^{1/2}E_{j}P=\beta_{ij}P + \Delta_{ij}$ where we have $\eta_{P} = \frac{1}{2}(1-t_{\textrm{min}})$. The $t_{\textrm{min}}$ are the minimum eigenvalues of $E_{j}$ and the $\Delta_{ij}$ is traceless.

In any case, she obtained a near-optimal recovery map for all channels with the optimality based on the worst-case fidelity (i.e. she used fidelity to identify her worst-case performance scenario for AQEC).

Following that, <NAME> gave a talk on the statistical mechanics of disordered quantum optimization. Basically – and I find this fascinating – P$\ne$NP apparently implies the existence of glassy physical systems. Now that’s wild. Now, the main crux of the talk was focused on more graph theoretic stuff. So, for instance, when they do stuff like this (applying graph theory to physical systems) you do things (as Moessner did) such as finding that the number of non-zero energy states depend on the properties of the graph. The punchline of his talk was that their methods provide improved lower bounds on the SAT-UNSAT transition (more complexity stuff).

<NAME> finished up the afternoon with a talk on a quantum Lovász lemma. A somewhat minor point I noticed was her “definition” of independent events. I’m still not entirely sure I agree (it’s the cosmologist in me talking). She “defines” them as, given two independent events, it means there is a non-zero probability that each occurs at some point. There’s something vaguely unsatisfying about this from a cosmological point of view, but I am also being cautious by putting things in quotes since her paper might be more rigorous. At any rate, her motivation, similar to the previous talk, revolved around K-SAT. Unfortunately, sitting in the airport almost two days later, I can’t read the rest of my own chicken scratch on the talk. My apologies to both readers and Julia on this.

The conference dinner was held at a lakeside restaurant. While very good, those of us who were still a bit jetlagged (like the poor Japanese guys next to me who had come in to town a bit later than me) started dozing. The main dish wasn’t served until 9 and dessert wasn’t served until 11. In the midst of this, <NAME> (who has shed his beard) gave a nice historical talk on the BB84 protocol. The gestation for the idea actually dated to 1970 and a guy who’s name I have since forgotten (did I mention I was exhausted?). It was a great talk and included plenty of discussion about the failures of getting the idea published. Basically, Gilles said that they couldn’t convince anyone until they built an actual prototype.

Friday morning began with a great talk by <NAME> in the principle of information causality. First, let me say that Marcin’s talk was by far one of the absolute funniest at the conference. He began with an awesome overview of just exactly what a physical principle is (this is so interesting from a foundational point of view). In relation to the idea of “reasonability” regarding communication between Alice and Bob, for instance, and relating to T’sirelson’s bound he really tried to explain why it is the way it is. He then began talking about mutual information and I SWEAR he was inches away from saying what I’ve said in my poster – mutual information is a statement of the second law, i.e. $H(A:B) \ge 0$ and $\Delta S \ge 0$ (for isolated systems and where S is the usual thermodynamic entropy) are really the same thing. Plus he brought causality into it which is another thing I’ve been ranting about for years (not that I’m sold on causality being a necessary condition, just that I know it can be related to this). In regards to information causality, the principle is that the sender decides what information is transmitted. I think I could relate this to my CTC communication protocol too, but I’ll have to think about it some more.

<NAME> and <NAME> followed with pretty good foundational talks, though I didn’t take too many notes at this point. Both used the CHSH inequalities (which is good stuff) and Boixo’s work assumed that quantum mechanics is at least good locally. His closing advice was “if you break something, break it big.”

I, alas, skipped the rest of the talks due to a melted brain and a stubborn insistence that I find Liechtenstein which I did (I’ll post pictures eventually). I even found a place to stamp my passport (since there are no official border crossings between Switzerland and Liechtenstein) thanks to a friendly truck driver whose wife is from Seattle. I also found the graveyard of famous astronomer Fritz Zwicky, but don’t think I actually found the real Fritz because there were several who were all about the same age! Every other name in the graveyard (which was the only one in town) was “Zwicky” and the local drug store was “Zwicky’s.” So I missed the actual grave apparently, but saw plenty of his relatives! I then drove up into the mountains until the road I was on was closed due to weather higher up. But I did see some wicked cool stuff up there and will – again – have pictures soon.

So, that was QIP 2010. It was a great experience despite my problems with the Program Committee and I thoroughly enjoyed Switzerland (though I need to bone up on my German for my next visit).

Posted in Uncategorized on January 21, 2010 by quantummoxie

I just got back from the workshop dinner and am going to sleep. But I’m taking a road trip again tomorrow – Lichtenstein (I WILL find it this time) and <NAME>’s grave in Mollis. If you’re at the conference, reading this, and want to join me, grab me at the morning session.

## QIP – Post 4 (Wednesday recap)

Posted in Uncategorized on January 21, 2010 by quantummoxie

Since it’s already Thursday, I want to give a recap of Wednesday.  I got back to my apartment rather late last night and didn’t get a chance to do the recap (more on why I was late in a bit).

The morning was kicked off by a pretty cool talk given by <NAME> on quantum coin flipping motivated by the idea that Alice and Bob don’t trust each other (there must be an opportunity for a joke in here somewhere…).  The interesting thing is that their construction is entirely classical except for the presence of a black box.  Given all the other interesting aspects of the results, this seemed the most interesting to me since it seems to say something about how the universe works, i.e. just how that black box interacts with the classical parts is, in essence, the quantum-classical boundary.  At any rate, they have a strong coin flip protocol that matches Kitaev’s bound with a probability of cheating of $z=2-\sqrt{2}$. Regarding their black box, it is a bit like a back-and-forth teleportation scheme in a way. Their methods used point (as in points on a graph) games as an example and what they were doing had many elements of a directed graph (so there are connections to some of Rob Spekkens’ work in here – in fact they interpret their results in terms of the Spekkens-Rudolph protocol). In this midst of the talk, young André had a “<NAME>” moment when his girlfriend Skyped him (Jan-Åke’s wife did the same thing in the midst of an APS talk he gave in Denver several years ago).

<NAME> (who shall forever after be referred to as “The Chairman” – you had to be there), gave a nice talk on highly entangled states that, oddly, offer absolutely no secrecy. Aside from some computer problems (note that all the non-Macs have had trouble with the display connection), The Chairman’s main question was if there was a “bound” key and the answer is that, yes, there is an asymptotically bound one. His results were broken into both symmetric (bosonic) and antisymmetric (fermionic) parts and he focused his talk on the latter. He had some great pictures tossed in (including a Platypus – gotta love the Platypus).

<NAME> followed with a talk about improved extractors for bounded quantum storage which is another interesting cryptography thing related to adversaries attempting to extract keys (oh those nasty adversaries). He was able to prove the security of his work using a proof by contradiction (I love seeing undergraduate stuff pop up in these talks).

I didn’t write down notes on most of <NAME>ann’s talk, but it was more cryptography stuff and sounded pretty cool. <NAME> followed with another talk on two-person cryptography (no Eve is present – essentially, do Alice and Bob trust one another?). In such a scheme, one might imagine Bob as an ATM machine and Alice is the customer. Now, on the one hand, Bob (the ATM) could be malicious, i.e. someone may have hacked in or maybe it’s not even a real ATM. So Bob could be distrustful. On the other hand, Alice might not be who she claims to be and thus she could be distrustful as well. Wehner’s group essentially attacks this really fascinating problem via another quantum bounded storage model.

<NAME> finished up the morning with a talk on unitarity and causality (yeah, now we’re getting somewhere, heh heh heh – or not depending on whether we’re causal – ok, nevermind). In any case, his talk contrasted a structuralist approach with an axiomatic one. In fact, his approach reconciled the two approaches to QCA. In the process he invoked index theory which is something I know almost nothing about. But I think I want to know more since he had an interesting take on the relation between causality and graphs. I need to ponder it some more before commenting in detail on it. The one thing that confused me a bit was his non-symmetric light cone. I wasn’t sure what his horizontal axis was since, in normal Minkowski space, it shouldn’t be non-symmetric but he didn’t seem to specify a different value for that axis and he wasn’t working in curved space (at least he didn’t seem to indicate he was). Anyway, the quantum case had a different (more symmetric) light-cone and he noted that this was the cost of apparently superluminal transmission of information.

Now, in the afternoon, <NAME> and I headed out (in a black Mercedes E-Class!) to find four things – at least one of Einstein’s houses, the grave of <NAME>, the grave of <NAME>, and the nation of Lichtenstein. We found all but Lichtenstein. If I were any nuttier than I am, I would SWEAR it doesn’t exist (a conspiracy of cartographers?). At least, the Swiss don’t really seem to acknowledge its importance as a country. It turns out we turned around 4 miles from the border and never once saw a sign indicating we were even close. Avis didn’t give me a map and the GPS system in the car was surprisingly bad considering it was a Mercedes. But I refuse to leave until I’ve been to Lichtenstein, so I might skip some of tomorrow’s sessions in order to get there. Regarding the others, I will have photos in due course. Pauli’s was pretty cool in the sense that it probably gets very few visitors. In order to find it, I had to ask a couple of guys who worked for a local floral place and were putting flowers on a recent grave. Neither spoke English and one (oddly the older one) had never heard of Pauli, but the younger one knew exactly what I was talking about (dumb American that I am – I really do wish the US did a better job of language education) and led us straight to it. Of course, <NAME> (of Hopf algebra fame) is buried right next to Pauli. Joyce’s grave was very nice too. There’s a nice statue of him next to it. Across the street happened to be the world headquarters of FIFA (that’s soccer’s international organization). Again, picture will be forthcoming.

Unfortunately I missed the rump session and thus Todd’s talk on umbrellas and – apparently – quantum animal husbandry. Perhaps Todd can enlighten us by linking to his talk…

format: plain


text:
<meta http-equiv="refresh" content="1; url=/nojavascript/"> Modeling and Simulation | CK-12 Foundation
You are reading an older version of this FlexBook® textbook: CK-12 21st Century Physics - A Compilation of Contemporary and Emerging Technologies Go to the latest version.

# 13.4: Modeling and Simulation

Difficulty Level: At Grade Created by: CK-12

In the simplest case where the rocket motor provides a constant upward acceleration and we neglect air drag, wind, and the rotation of the Earth (not a realistic assumption for an actual rocket), the motion can be solved in closed form with relatively simple algebra. However, as we add air drag and model the rocket engine more realistically, we have to resort to solving differential equations. Ultimately, a numerical simulation using a computer is called for. <NAME> (1707-1783) developed a conceptually simple method for numerically solving equations like those we will deal with. The method involves rates of change and equations that can’t be solved with algebra. Although there are more sophisticated and efficient numerical methods, modern computers are fast enough that we will be able to get by with Euler’s conceptually simpler method. It is very powerful in its simplicity.

## Approach to Learning

Students can learn a lot by looking at examples of how others solved a particular problem and then modifying the solution to adapt the problem to less stringent assumptions. It is in the modification process that the student’s understanding of the solution is tested and where valuable learning takes place. We will follow that process in this chapter. Using Etoys, a simulation of the rocket, with simplifying assumptions will be available for the learner to modify to a more realistic solution. As more complexity is included along the way, the learner will be rewarded with a sense of accomplishment and a deeper understanding of modeling, simulation and motion.

## General Assumptions

We start by making several assumptions to simplify the problem of the LAS and relax several of them as we approach a more realistic model.

1. The acceleration of gravity is constant at 9.8 m/s2. This is a reasonable assumption near the surface of the earth, but at the International Space Station, that acceleration has already dropped to around 0.9 the value that it has at the Earth’s surface. We can relax this assumption without too much effort.
2. We will neglect air resistance. This isn’t a reasonable assumption and it is one of the first we will attack with Euler’s method.
3. The rocket engine will be modeled as providing a constant upward acceleration. This isn’t realistic and we will later model the rocket engine with a constant gas exhaust velocity relative to the rocket and a constant rate of mass decrease of the rocket fuel. However, we won’t be able to model the actual engine used by NASA, as that is proprietary information – proprietary information is information or intellectual property owned by a company and protected from unauthorized distribution for the purpose of allowing the company to make money.
4. We will neglect the fact that Earth is rotating. Newton’s laws apply in a coordinate system that isn’t accelerating. Because the Earth rotates about its axis, a coordinate system attached to the Earth from which we observe the motion, is accelerating. Anything moving in a circle accelerates because the direction of the velocity is always changing. Velocity is a vector and has both magnitude and direction. If either the direction or magnitude changes, the velocity changes and the object is said to accelerate. The acceleration of a point on the equator is around 0.034 m/s2. Although this is a small fraction of g, the effect is very noticeable for the range of motion of a typical rocket. In addition there is a smaller acceleration because the Earth revolves around the Sun 0.006 m/s2 and an even smaller one because the Sun revolves about the center of our Milky Way galaxy 2.4 x 10 -10 m/s2, and so on... It isn’t easy to do physics calculations in a rotating coordinate system and we will leave that as an independent investigation for the learner. Read about the Coriolis effect (Gaspard-Gustave Coriolis 1792-1843) if this topic interests you.
5. We will neglect forces from winds.
6. We will neglect departures of the Earth from a uniform sphere.
7. We will neglect the buoyant force of the Earth’s atmosphere on the rocket.

## Model 1: Constant Acceleration in One Dimension

We could solve some of the models using algebra and others would require solving differential equations, which requires a greater mathematical sophistication. Although we could use closed form techniques, we will use the Euler method, which is conceptually simple, powerful and can be used to solve nearly any problem given enough computing power and time. Learning to solve problems numerically is a valuable skill to have. We will start modeling the rocket engine as providing a constant upward acceleration of the rocket, which moves upward in one dimension until the burn is completed. Once the burn is finished, the rocket will be in freefall as we will neglect air resistance and winds. We will ignore the fact that we are in a rotating coordinate system.

### Description

You can access this model after downloading and installing Etoys at squeakland.org. The URL for the model is http://www.pcs.cnu.edu/~rcaton/flexbook/flexbook.html If you can’t find a computer where you can install Etoys, it is possible to run the simulation off a memory stick. You can download a copy of Etoys-To-Go at squeakland.org and the simulation at http://www.pcs.cnu.edu/~rcaton/flexbook/flexbook.html The simulation is an Etoys project with an extension .pr. If the downloading process puts a .txt extension on the end, remove the .txt extension. You need to unzip the downloaded file and put Etoys-To-Go and the simulation on the same memory stick. The simulation .pr file should go in the Etoys directory.

### Experimental Observation and Understanding

Scientists and engineers find it useful to plot data on a graph to visualize what is happening and you will too. Before modifying the simulation, it is instructive to take data on the simple model in the Etoys project.

Exploration 1: To start collecting data, set your values for burn time and acceleration in the Control and Data Center, click the yellow reset button, record the time and altitude, click the red launch button, click the yellow pause button approximately every second, record your new data, and click the red launch button to resume. Take data until 10 seconds after the burn time is over. Plot the position on the vertical axis against the time on the horizontal axis. Work in groups and brainstorm how you should best collect and record the data. Have each member choose different burn times and accelerations for the rocket. Discuss your results in the group and compare with others' data and plots.

1. How does the burn time affect your graph's shape?
2. How does the acceleration affect your graph's shape?

Exploration 2: Record data in your notebook on the velocity of the rocket approximately every second until 10 seconds after the rocket's burn time is over. Plot the velocity on the vertical axis against the time on the horizontal axis. Work in groups and brainstorm how you should best collect and record the data. Have each member choose different burn times and accelerations for the rocket. Discuss your results in the group and compare with others' data and plots.

1. What is special about the shape of your graph? Remember, there is always error in real data, so your graph may not be perfect. Try to visualize what the ideal graph would look like.
2. How does the burn time affect your graph's shape?
3. How does the acceleration affect your graph's shape?

Exploration 3: What would happen if you launched the rocket on the Moon or a planet other than Earth? Work in groups and have each member find a value for the acceleration of gravity at the surface of the Moon or planet. Use books and the Internet. Be sure the units are meters per second per second so you can compare with the value given for Earth. If the values are in different units, look up how to convert the values to the needed units. Enter the new gravity values in the second from bottom box in the Control and Data Center. Take data on the new motions and plot it. Discuss your results in the group and compare with others' data and plots.

## Model 2: Air Resistance

We will relax some of the simplifying assumptions one at a time starting with air resistance. For large objects like the CEV, the air resistance can be modeled as producing a force proportional to the square of the speed and opposing the motion of the object. Your assignment is to add this to the previous model by modifying the force expressions for the two regions: the constant acceleration upward while the rocket engines are burning and the subsequent freefall. It would be wise to include a proportionality constant in the air resistance term so you can vary the strength of the force of the air on the rocket. Although Euler’s method is used in the simulation, it would be good to explicitly present the notation here.

Because y and vy are constantly changing with time, they need to be continually updated. Take a small step in time dt to change y and vy. Calculate the new values for y and vy using

${\mathbf{\color{red}y}} &= {\mathbf{\color{green}y}} + dy = {\mathbf{\color{green}y}} + {\mathbf{\color{green}v_y}}dt\\{\mathbf{\color{red}v_y}} &= {\mathbf{\color{green}v_y}} + dv_y = {\mathbf{\color{green}v_y}} + (a_y)dt\\a_y &= \frac{F_y}{m}$

For example, $F_y = (-mg + kv^2)$, with k positive when the rocket is freely falling toward Earth. You need to figure out the other cases during the motion. The green values are current values of y and vy and the red are the new values. The amazing thing is that for small enough dt the result approaches the correct solution with arbitrary precision for well behaved systems.

## Model 3: A More Realistic Rocket

Rockets aren’t usually designed to provide a constant upward acceleration. Although we can’t divulge the proprietary propulsion scheme, a first step in modeling a more realistic rocket is to assume a constant burn rate for the fuel and a constant ejection speed of gas relative to the rocket. The force on a rocket taking off from Earth has two components: one from the gravitational force of the Earth and the other from the expulsion of gases from the rocket engine (thrust). We will continue to neglect the rotation of the Earth and small variations in the acceleration of gravity from height above the Earth and departures of the Earth from a perfect uniform sphere. The discussion below leaves out air resistance. You can add it if you wish.

Call M the mass of the rocket. The force of gravity is -Mg if we take upward as positive and assume we are near the Earth's surface where g is fairly constant. The rocket force can be found from the impulse momentum theorem: Frdt = -vedM because dM (the small change in M) is negative. ve is the velocity of the ejected gas relative to the rocket. We assume that dM/dt ( = -C) and ve are constant to make the problem easier. The total force can be written as

$F = -Mg - (v_e) \left (\frac{dM}{dt} \right )$

We get the following finite differentials:

$dM &= -Cdt\\dy &= v_y dt \ (y \ \text{is upward})\\dv_y &= a_ydt = \left (\frac{-g - v_e \left (\frac{dM}{dt}\right )}{M} \right ) dt$

Because y, vy and M are constantly changing with time, they need to be continually updated. Take a small step in time dt to change M, y and vy. Calculate the new values for M, y and vy using

${\mathbf{\color{red}M}} &= {\mathbf{\color{green}M}} + dM = {\mathbf{\color{green}M}} -Cdt\\{\mathbf{\color{red}y}} &= {\mathbf{\color{green}y}} + dy = y + {\mathbf{\color{green}v_y}}dt\\{\mathbf{\color{red}v_y}} &= {\mathbf{\color{green}v_y}} + dv_y = {\mathbf{\color{green}v_y}} + \left (\frac{-g - v_e (-C)}{{\mathbf{\color{green}M}}} \right )dt$

The green values are current values of M, y and vy and the red are the new values. Again for small enough dt the result approaches the correct solution with arbitrary precision for well--behaved systems.

Your assignment is to modify the previous model to use the more realistic rocket engine described above. You can include air resistance if you wish, but it may be best to leave it out at first until you have the rocket engine model working properly. You can get some numbers to test your model from Physics by Alonso and Finn (p. 136).

## Model 4: Accounting for the Change in Gravity as the Distance from the Earth Changes

Earth’s force of gravity reduces as the rocket’s distance from Earth increases. To model this, assume an Earth with spherically symmetrically distributed matter and then you can replace the Earth with a point mass at its center. Newton held up publication his Principia until he could prove this was true. For the LAS at the launch pad, the variation of the force of gravity isn’t a big effect because the CEV doesn’t get that far from the Earth’s surface, but it is valuable for your education to model this behavior.

## Model 5: Simplified LAS

Figure 3: Scope of LAS Operating Environment. (Attribution: NASA)

A simplified 2D model of the LAS implemented in Etoys can be downloaded at http://www.pcs.cnu.edu/~rcaton/flexbook/flexbook.html. Explore this model to learn how it works. A simulation with changing mass would be a much better representation. The LAS + CM loses about a 7th of its mass during the abort motor burn. We used a simplified thrust curve for the abort motor because the actual thrust curve is “NASA sensitive.”

## Extensions

Adapt the 2D LAS model to employ a rocket with constant exhaust velocity and constant rate of mass loss. Model a two-stage 1D rocket.

Feb 23, 2012

Nov 25, 2014


text:
Archive

Archive for May, 2012

Thoughts on memoization

As I said in the previous post about GSoC, recently I started to think about how to implement random access to BAM file (which consists of gzipped blocks about 20kbytes each).

The problem is, we have a decompression function which is computationally intensive, and we are to convert requested blocks in the most efficient way, preferably using multithreading.

Let’s generalize it. We have a function $f: X \to Y$. What we want is the same function but returning the result faster. However, that’s not a good idea because it will be hard to parallelize iteration over a subset of $X$. It’s better to define a memoization operator $M$ mapping $f$ to $Mf: X \to D_Y$ which will return a delay instead of actual value. To work with this delay, we need another function $g: D_Y \to Y$ such that $f = g \circ Mf$. The nice thing about this approach is that the delay can be returned immediately, while computation can be done in another thread.

Thus we can get both things working:

• Parallel map. We can use a cyclic buffer of delays, prefilling it at the start. This way, there will always be a fixed amount of tasks being executed in a multithreaded task pool. Advancing to the next element will be accompanied with pushing new task into the pool.
• Evaluation at random points. Memoization operator can maintain a cache of delays, to which access will be syncronized.

I googled these idea and found this great article: http://kotka.de/blog/2010/03/memoize_done_right.html. It contains some code in Clojure, and particularly, it contains an implementation described above, using futures and cache with synchronized access.

Converting that code to D shouldn’t be a big problem thanks to std.parallelism module providing future/promise stuff. I currently aim at developing a reusable solution built on templates and allowing arbitrary function and cache implementation.

(to be continued…)

Categories: Uncategorized

GSoC weekly report #2

Ruby bindings

Now it’s possible to iterate over alignments from Ruby, although it’s much slower than doing the same from D. Iterating will make more sense when I’ll introduce filtering and random access. But anyway, Ruby syntax can be used for iteration, and it looks nice:

bam = BamFile.new "test/data/ex1_header.bam"
puts bam.alignments
.compact                      # remove nils
.instance_eval { reduce(:+) / size.to_f } # get average

Validation

This week, I concentrated mostly on validation module. As I haven’t yet developed deep understanding of NGS technologies, I just did my best on translating all ‘must’, ‘ought to’, and ‘shall’ appearing in the specification, into program code :)

The results are good enough – my validator has catched a few errors in tags.bam provided by <NAME>, all of them about invalid characters in read names and tags (spaces and @). That’s the output:

ReadNameContainsInvalidCharacters in read 'tag_zz:Z: '
Tag error: NonPrintableCharacter ('aa' -> 'A: ')

I tried to design my validation module to be customizable. Therefore t works this way: if you need to validate, say, alignments, you subclass AbstractAlignmentValidator, implement your own error handlers, and then use its ‘validate’ method for alignments.

class Validator : AbstractAlignmentValidator {
void onError(ref Alignment alignment, AlignmentError e) {
}

void onError(ref Alignment alignment, CigarError e) {
writeln("\tCIGAR error: ", e);
writeln("\t\t   cigar string: ", alignment.cigar_string);
writeln("\t\tsequence length: ", alignment.sequence_length);
}

void onError(string key, ref Value value, TagError e) {
writeln("\tTag error: ", e , " ('", key, "' -> '", value.to_sam(), "')");
}
}

Notice that if you’re too lazy to implement all abstract methods, you can use std.typecons and subclass BlackHole!AbstractAlignmentValidator ;-)

Currently, there’re 8 types of alignment errors, 3 – of CIGAR ones (I’m sure there should be more of them), 10 – of errors in tags, and about 10 – of SAM header errors which are catched with another abstract class.

Tags

By the way, have you noticed this Value type used in tag error handler? It’s a C-style tagged union with a bunch of methods which play well with typical D code. You can assign it to a variable of any type allowed by the specification, compare, get the stored value (standard ConvException is thrown if wrong type is requested), and convert it to SAM format that easy:

short[] array_of_shorts = [4, 5, 6];
Value v = array_of_shorts;
assert(v.is_numeric_array);
assert(v.to_sam == "B:s,4,5,6");
assert(to!(short[])(v) == array_of_shorts);

I also attempted to provide this kind of facility for Ruby. For instance, ‘tags’ method of an alignment returns a Hash with objects of corresponding Ruby types, be it arrays of integers, strings, or whatever.

Random access

Yesterday I started getting my head around how random access works. Now I already have something working, but it’s probably very buggy. And slow (no caching yet). And works with DMD only :(

Even with DMD I had to tweak my code in several places in order to avoid internal compiler errors. It’s somehow related to passing delegates as template arguments to standard library algorithms. Functional style suits my thinking, but the two compilers are not ready for that. The errors I saw from GDC were truly astonishing! 14k characters long mangled function name is something unforgettable :) Here it is: https://gist.github.com/2802993

Since I’ve almost finished my plans for the second week (Ruby bindings just need some polishing), I’m going to continue playing with random access stuff next week. If I’ll manage to get it working before July (for when it is planned), I’ll probably try to implement indexing then, and maybe even investigate indexing schemes other than the default one, i.e. BAI. The rumors are, BAMTools has its own index format, BTI, which makes for faster random accesses, up to 10x. (http://bioinformatics.oxfordjournals.org/content/27/12/1691.full)

Categories: programming Tags: ,

GSoC weekly report #1

The coding period has finally started. I’m glad to become a part of BioRuby community which is, fortunately, a very friendly one :)

The past week saw a lot of activities of various sorts, so this particular report is a bit long.

Rubinius issues and BioRuby unit tests

I filed two bugs to Rubinius bug tracker. One is already fixed, and that will solve some of unit test failures. Also another bug in String#split was fixed recently, and I expect that after the next update Rubinius will pass all unit tests in 1.8 mode on Travis CI.

The situation with 1.9 mode is a little more complicated. For instance, it doesn’t yet fully implements IO#popen and Kernel#Spawn method semantics, and that causes Bio::Command to behave incorrectly. I filed a bug yesterday about that.

I will continue to investigate which Rubinius bugs cause unit test failures. I like LLVM in general, and this implementation of Ruby in particular. JIT compiler + no JVM dependency + clean code… Not that fast yet, but improvements are definitely possible. Clang already outperforms GCC in some cases ;)

D code optimizations

I started a wiki page on github: https://github.com/lomereiter/BAMread/wiki/D-optimization-techniques

Currently, it contains 6 small tips, and I expect it to grow during the summer.

BDD

Also, I learned a bit about behaviour-driven development in general, and about Cucumber. I really like this approach :) It’s very motivating to see at a glance what needed, why, and by whom. And splitting everything into scenarios and steps allows to easily divide one milestone into several smaller ones. I would anyway keep all those things in my head, and it’s cool that written in Gherkin, they can drive my development and serve testing and documentation purposes :)

Ruby object creation time

During previous week, I optimized my BAM reading library quite a bit. Currently, it uses std.parallelism.parallelMap to unpack BGZF blocks in parallel. What I wonder, though, is does it make any sense to be able to iterate alignments from Ruby?

Let’s take some big file and see how long it takes to parse it serially:

$./readbam ../HG00476.chrom11.ILLUMINA.bwa.CHS.low_coverage.20111114.bam unpacking took 24925ms number of records: 10585955 OK, and how long does it take to create corresponding number of Ruby objects? (Ruby 1.9.3-p194) $ ruby -rbenchmark -e 'p Benchmark::measure{10585955.times{Object.new}}.total'
4.54

Compared to 25 seconds, it doesn’t look that bad.

But let’s try parallel version (thanks to Pjotr, I can use a 8-core server via SSH):

\$ ./readbam ../HG00476.chrom11.ILLUMINA.bwa.CHS.low_coverage.20111114.bam 7
unpacking took 6733ms
number of records: 10585955

Hmm, so if we use one object per alignment, it will take at least 4.5s to just create all of them in Ruby, while D code will parse 2/3 of the file in that time.

And if we create not Objects, but FFI Structs like this simple one:

class S < FFI::Struct
layout :dummy, :int
end

things get worse — creation of 10M objects of this class takes almost 20 seconds. Well, one might argue it’s not that bad either, for 0.8GB file…

…but in fact, I see no use cases for iterating alignments from Ruby (although I’ve somehow managed to write Cucumber feature for that). My library will provide heavily optimized functions for common high-level tasks to be used from dynamic languages. Whenever you want speed — write code in D. Whenever you want interactiveness (e.g., fetch alignments overlapping particular region and visualize them somehow) — use your favourite dynamic language, the library will provide such functions. Both these things should be easy, that’s what I aim at.

Categories: programming Tags:

GSoC weekly report #0.5

So, another week of “pre-coding” period have passed.

I was mainly concentrated on D part of the project, adding functionality to it. During the week, I implemented parsing of the whole BAM file :) Today I wrote a simple utility in D, which uses my library to convert BAM to SAM. It doesn’t work with array tags yet, and not as fast as samtools, but nevertheless… On a couple of BAM files from test/data directory (namely, bins.bam and ex1_header.bam) the output is identical to that of samtools view — I checked with diff — and that kinda proves that everything works fine. Speed issues are mainly due to using std.variant module for storing tags. It uses runtime reflection which is quite slow. Maybe, there’re some other reasons. Anyway, I’m going to write my own tagged union type next week, it should improve the performance quite a bit, and also fix design flaws.

For testing tag parsing, I used file tags.bam provided to me by <NAME>. It contains tests for all types of tags, and my library successfully passes them. Later I’ll experiment with possible speed improvements, and having unit tests covering full range of possible tag types is a must.

Also, I downloaded and compiled gdc from trunk. It provides decent performance, not worse than dmd, at least. We expect gdc to gain shared library support in the next two months. Before that happens, we have to use dmd, although there’re some issues with its garbage collector, causing segfaults. We discussed that with Marjan and Pjotr and decided that the best option in such circumstances would be to disable GC during development — testing library on small files won’t consume much memory anyway.

Another thing I downloaded and compiled is Rubinius. I’m going to investigate why it hangs on BioRuby unittests in 1.9 mode. Another mode, 1.8, seems to work fine except maybe some very minor bugs.

During next week, I’m going to learn how to use Cucumber and Rspec, improve D library performance a little, and start to write Ruby bindings. So it will be mostly ‘Ruby week’ ;-)

Categories: programming Tags:

[GSoC] Weekly report #0

Finally, OBF seems to be convinced about usefulness of new BAM parser. Thus now I can spend time on coding instead of writing/talking on why what I’m about to do is so important :)

I began to write code before the official start for two reasons. First, I just can’t wait to get my hands on this. The project is a great opportunity to learn more about D and Ruby, and what they’re capable of when being combined. By the way, it’s one of the goals we set for this summer — discover some best practices. Moreover, I’ll describe some techniques I already use, in this very post ;) The second reason is more prosaic. I’ll have exams in June, and therefore I have to do some stuff in advance. However, I believe I’ll deal with time management issues. Since July I’ll be able to work mostly full-time.

Now let’s move on to what was done during last week. The project repository is at https://github.com/lomereiter/sambamba. Directory structure is not well organized yet, I’ll do that a bit later.

The main struct, BamFile (bamfile.d), has just a constructor, method close() and, the most important at the moment, header property which returns SamHeader struct (defined in samheader.d).

Now I advise you to take a look at samheader.d. It is rather small file which begins with ~50 lines of rather crazy mixture of string mixins and mixin templates, and then…

mixin HeaderLineStruct!("SqLine",
Field!("sequence_name", "SN"),
Field!("sequence_length", "LN", uint),
Field!("assembly", "AS"),
Field!("md5", "M5"),
Field!("species", "SP"),
Field!("uri", "UR"));

That’s how I want to define structs for information from SAM header line fields. And D allows me to do that. This code generates struct definition, with static method parse() which takes a string and returns an instance of the struct. Really, if “each line is TAB-delimited and except the @CO lines, each data field follows a format ‘TAG:VALUE’ where TAG is a two-letter string <…>”, why should I write more than this tag and the type of the value? And since the value type is almost always a string, let’s make it default in the Field template ;-)

So, here’s the first useful technique: whenever you find some code to be too repetitive, see if it’s worthwhile to create a small DSL based on mixins. D makes code generation easy with compile-time function evaluation, almost as easy as writing Lisp macros.

How about writing Ruby FFI bindings to these structs? I decided to apply DRY principle again, and here’s my another idea: scaffolding. RoR guys have been doing automatic boilerplate generation for years, so why not apply this method for generating FFI bindings?

So I wrote a small Ruby code generator for D structs, which currently supports numeric types, strings, and arrays as struct fields. Now just a few lines of code will do:

import samheader;
mixin(import("utils/scaffold.d"));

import std.stdio;

void main() {
File("bindings/scaffolds/SqLine.rb", "w").write(toRuby!SqLine);
File("bindings/scaffolds/RgLine.rb", "w").write(toRuby!RgLine);
File("bindings/scaffolds/PgLine.rb", "w").write(toRuby!PgLine);
}

The results of generation are in bindings/scaffolds. Since Ruby has Open Classes, you can reopen any class and define/undefine its methods. For instance, I haven’t found a way to determine at compile-time whether a field is private or not, and you might want to undef corresponding methods. However, there is a thread on dlang.org with suggestion to add getProtection trait. Hopefully, it will be added to the language in the near future.
With a few lines of hand-coded bindings, we can use D functions from Ruby:

load './bindings/libbam.rb'

bam = BamFile.new "HG00125.chrom20.ILLUMINA.bwa.GBR.low_coverage.20111114.bam"

The code lacks tests and documentation, though, and that’s what I’ll be working on during the next week.

Categories: programming Tags: , ,

It turned out to be really easy, using std.stream and std.zlib modules :)

Sequence of actions is as follows:

1. Create an instance of BufferedFile, providing file name to its constructor.
2. Then pass it to constructor of EndianStream, specifying little endian byte order
3. Read BGZF blocks from this stream, according to their specification, and decompress them using std.zlib uncompress function (winbits must be -15).
4. Then the range of decompressed blocks is being wrapped by subclass of Stream, using MemoryStream internally. To make a Stream subclass, you only need to define just three methods: readBlock, writeBlock, and seek. The latter two may just throw an exception in this partucular case. That took me as little as 64 lines of code.
5. Now that we have this full-fledged stream, we again pass it to EndianStream constructor. And then we can read BAM data from it.
About 200 lines in total. That’s how powerful D standard library is. Much like Python ‘batteries’ ;-) And what I like the most, comparing D to C++, are ranges instead of STL iterators. They are really easier to write and easier to use, at least for iterating when the length is not known in advance. Calling empty() is way more intuitive than comparing with some idiotic default iterator indicating end of stream, like it’s done with istreambuf_iterator.

Now that I’ve learned how to read data from BAM, next step will be SAM header parsing. The header is typically small, about a hundred of lines, only in extraordinary cases being more than 4MB, so it makes little sense to optimize speed. Better to spend more time on validation part.

Categories: programming Tags: ,

On programming languages and HPC

Some people believe one should never rewrite old code. I’m not among them, and let me tell why, taking samtools as an example.

If you want your programs to scale on modern multicores, you must use parallelism. Free lunch is over, damn it! It’s great that samtools’ authors realize that, but hey, do you really want to add 40 lines of code each time you need a trivial parallel for loop?

Modern languages make such stuff easy to use, and moreover, when it’s in a standard library, whenever someone comes up with the idea how to make some routine faster, you get this performance boost automatically with the new version. Conversely, if this ‘someone’ is you, you will help not only yourself but the whole community. It’s all about not reinventing the wheel and code reuse.

I’m sorry to say this, but to me, a lot of C coders seem a bit like cavemen. I’ve seen a lot of examples of using home-made object system, or string library, or container/algorithm library. They live without generic programming, and when they come to the point where even macros are of no help, they roll out their own code generators in Ruby/Python/etc. The situation with OOP is a bit better because of GObject existence. As for multithreading, I would advise many of them to study OpenMP and look if it’s suitable for their tasks. (That’s KISS principle.) And only if it is not, this is the case for pthread.h.

Well, one could ask, how about reusing old code? The thing is, in this particular case, samtools were not designed to be used as API. All the existing bindings to dynamic languages arose out of necessity. To appreciate what a pain in the ass it is, I advise you to read how <NAME> describes his experience with creating bindings. Seems like nobody ever gave a damn about refactoring.

Now, why are we so concerned about having API, shared libraries, and dynamic languages? Scientists love DSLs, and R is the brightest example for that. In the absence of DSL, one uses some dynamic language so as to concentrate on his/her tasks instead of fighting with language quirks. Many people also like interactiveness, i.e. having REPL environment with ability to visualize data they’re working with. But dynamic languages are usually slow, and that’s the reason we have to use compiled code. There is some progress in creating languages both fast and dynamic, e.g. Julia, but it’s far too experimental at the moment.

And we don’t want to duplicate efforts in creating language bindings. At the moment, we have SWIG for C/C++, and GObject Introspection for Vala is being developed. There’re some developments for D, namely, RuDy and PyD. D is great in that it allows to generate C wrappers at compile time — you shouldn’t use a separate parser, just use __traits keyword and std.traits module. And compile-time function evaluation works well enough to write even compile-time raytracer.

Another point why D matters, in my opinion, is generic programming. Science is all about abstractions. I feel uncomfortable writing low-level code and being unable to express them in the most appropriate way, not losing any execution speed along the road. C++11 is another good language, though the template syntax is weird and opportunities are limited compared to D. Other than that, I see no languages supporting compile-time generic programming.

So, as I see it, new high-performance scientific libraries should be written in Cilk Plus or D. In my opinion, that’s the best way for them to be maintainable, generic, extremely fast, and easily bindable altogether. Another option would be to have a lot of domain-specific languages compiling to native code or using JIT compiler, like BioScala. Time shall tell…

Categories: Uncategorized Tags:


text:
Location of Repository

## Typical distances in ultrasmall random networks

### Abstract

We show that in preferential attachment models with power-law exponent $\tau\in(2,3)$ the distance between randomly chosen vertices in the giant component is asymptotically equal to $(4+o(1))\, \frac{\log\log N}{-\log (\tau-2)}$, where $N$ denotes the number of nodes. This is twice the value obtained for several types of configuration models with the same power-law exponent. The extra factor reveals the different structure of typical shortest paths in preferential attachment graphs.Comment: 16 page

Topics: Mathematics - Probability, Mathematics - Combinatorics, Primary 05C80, Secondary 60C05, 90B15
Year: 2011
OAI identifier: oai:arXiv.org:1102.5680


text:
1. ## Fraction Integration

Q: $\displaystyle \displaystyle\int^1_0 \frac{1}{3+t^2} \, \mathrm{d}t$

This is a follow on after I've substituted the $\displaystyle t$ value that they asked for. Can someone do this? Thanks in advance.

2. Originally Posted by Air
Q: $\displaystyle \displaystyle\int^1_0 \frac{1}{3+t^2} \, \mathrm{d}t$

This is a follow on after I've substituted the $\displaystyle t$ value that they asked for. Can someone do this? Thanks in advance.
Hello,

$\displaystyle \frac{1}{3+t^2}=\frac 13 \cdot \frac{1}{1+(t/\sqrt{3})^2}$, right ?

Substitute $\displaystyle u=\frac{t}{\sqrt{3}}$


text:
# Why Coriolis force is maximum at Pole?

The Coriolis force is directly proportional to the angle of latitude. As the latitude at which horizontally and freely moving objects are located increases, the twisting of the underlying Earth’s surface due to the planet’s rotation increases. That is the Coriolis effect increases as the latitude increases. It is maximum at the poles and is absent at the equator.