text:
Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.

For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.

Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [2,1,3]
Output: 1
Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.

Example 2:

Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same BST:
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: There are no other orderings of nums that will yield the same BST.

Example 4:

Input: nums = [3,1,2,5,4,6]
Output: 19

Example 5:

Input: nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
Output: 216212978
Explanation: The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^9 + 7 gives 216212978.

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= nums.length
• All integers in nums are distinct.

## Solution: Recursion + Combinatorics

For a given root (first element of the array), we can split the array into left children (nums[i] < nums[0]) and right children (nums[i] > nums[0]). Assuming there are l nodes for the left and r nodes for the right. We have C(l + r, l) different ways to insert l elements into a (l + r) sized array. Within node l / r nodes, we have ways(left) / ways(right) different ways to re-arrange those nodes. So the total # of ways is:
C(l + r, l) * ways(l) * ways(r)
Don’t forget to minus one for the final answer.

Time complexity: O(n^2)
Space complexity: O(n^2)

## python3

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode


text:
# Thread: True or false linear transformation

1. ## True or false linear transformation

Are the following true or false? If it is true, prove it, if it is false give a counter example (and proof that your counter example is true).

1) If T is a linear transformation such that T: $R^2$ -> $R^3$, T can't be one to one.

2) If a matrix has characteristic polynomial $f(x) = (x-2)^2(x+4)(x-4)$, then the matrx is not diagonalizable.

2. Originally Posted by cindy
Are the following true or false? If it is true, prove it, if it is false give a counter example (and proof that your counter example is true).

1) If T is a linear transformation such that T: $R^2$ -> $R^3$, T can't be one to one.
$T(x,y)=(x,y,0)$ is one to one.
May be you should ask $T:\mathbb{R}^{3}\to\mathbb{R}^{2}$?

3. Originally Posted by cindy
1) If T is a linear transformation such that T: $R^2$ -> $R^3$, T can't be one to one.
Like bkarpuz said it should be the other way around if you want to have an impossibility.
In general $T: \mathbb{R}^n \to \mathbb{R}^m$ is not one-to-one if $n>m$ by rank-nullity theorem.

2) If a matrix has characteristic polynomial $f(x) = (x-2)^2(x+4)(x-4)$, then the matrx is not diagonalizable.
$\begin{bmatrix} 2&0&0&0\\0&2&0&0\\0&0&-4&0\\0&0&0&4 \end{bmatrix}$

format: plain


text:
# Codeforces problem python code optimization

I have solved one problem on Codeforces and I guess the output is quite correct. However, it is slow for input in range of thousands. Since, I am learning Python now, it would be great help if one could help me optimise this code. Any notes, tips or suggestions on the sidelines are always welcome.

The question is a practice question and hence does not violate any contest rules.

import sys
import time

_no_of_ants, _no_of_queries = (input().split())
no_of_ants = int(_no_of_ants)
no_of_queries = int(_no_of_queries)

class ants_cord():
def __init__(self,point,no_of_ants):
self.co_ant = {point:no_of_ants}

def ants_at_point(self,point):
return self.co_ant[point]

def move_ants(self,point):
x1,y1 = point
if (x1+1,y1) in self.co_ant.keys():
self.co_ant[((x1+1),y1)] += 1
else:
self.co_ant[((x1+1),y1)] = 1
if (x1,y1+1) in self.co_ant.keys():
self.co_ant[((x1),y1+1)] += 1
else:
self.co_ant[((x1),y1+1)] = 1
if (x1,y1-1) in self.co_ant.keys():
self.co_ant[((x1),y1-1)] += 1
else:
self.co_ant[((x1),y1-1)] = 1
if (x1-1,y1) in self.co_ant.keys():
self.co_ant[((x1-1),y1)] += 1
else:
self.co_ant[((x1-1),y1)] = 1
self.co_ant[point] -= 4

def check_status(self):
for key in self.co_ant.keys():
if k.co_ant[key] >= 4:
return key
else: return False
start = time.time()
k = ants_cord((0,0),no_of_ants)
point = k.check_status()
while point:
k.move_ants(point)
point = k.check_status()
end = time.time()
print("Sec:{}".format(end-start))
while no_of_queries:
_x,_y = input().split()
x = int(_x)
y = int(_y)
if (x,y) in k.co_ant:
print(k.co_ant[(x,y)])
else:
print('0')
no_of_queries -= 1

EDIT: I updated the code according to suggestion. But I still get a TLE error in test case 4. Should I employ other algorithm then?

• I've added an answer. I don't have the right version of python handy but it should again make your script orders of magnitude faster. I'd be interested in the results if you were to perform performances tests with a high number of ants. – SylvainD Jun 24 '13 at 14:51
• I'm not sure that the task is solvable using python or any interpreted language at all. As you can see there aren't any python/ruby/.. solution and the fastest c++ solution time is 100 ms, so it's just impossible to run faster than may be ~2-5 seconds for a python solution. There is the list of failed (due to time limit) solutions - just apply the status filter (Python 2 or Python 3 and the Verdict like the 'Time limit...'). – cat_baxter Jun 24 '13 at 15:29

Here are a few improvements you could perform on the algorithm itself :

• You could simulate many iterations in one go.

In order to do so,

def move_ants(g,point):
x,y = point
for a,b in [(x+1,y),(x,y+1),(x,y-1),(x-1,y)]: # or you could define x generxtor
g[a,b] = 1 + g.get((a,b),0)
g[point] -= 4

could be changed for :

def move_ants(g,point):
x,y = point
nb_ants = g[point]
nb_ants_per_dir = nb_ants/4
for a,b in [(x+1,y),(x,y+1),(x,y-1),(x-1,y)]: # or you could define x generxtor
g[a,b] = nb_ants_per_dir + g.get((a,b),0)
g[point] = nb_ants - 4 * nb_ants_per_dir

• check_status could return a set of points to be handled

You'd just need to do something like :

def check_status(g):
return [k for k,v in g.iteritems() if v >= 4]

• Also, you might want to keep track of the cells you've updated in order no to loop over the all dict but only the candidates. This would need quite a lot of rewritting.

• Also, you could take into account the fact that the problem offer many axis of symetry : obviously the x and y axis but also the y=x and the y=-x. Thus you could restrict yourself to 1/8 of the plan corresponding to 0 < x < y

Edit

After testing, this code on 5555 ants:

  def move_ants(g,points):
cand=set()
for point in points:
x,y = point
nb_ants = g[point]
nb_ants_per_dir = nb_ants/4
for a,b in [(x+1,y),(x,y+1),(x,y-1),(x-1,y)]: # or you could define x generxtor
new_nb = g.get((a,b),0) + nb_ants_per_dir
g[a,b] = new_nb
if new_nb >= 4:
g[point] = nb_ants - 4*nb_ants_per_dir
return cand

g = {(0,0) : no_of_ants} # or you could use default dict
points = [(0,0)]
while points:
points = move_ants(g,points)
print("Sec:{}".format(time.time()-start))
for q in xrange(no_of_queries):
x,y=1,1
print(g.get((x,y),0))

appears to be 21 times faster than the solution provided in my other answer and 141 times faster than yours.

A few things:

• You should probably put the start = time.time() as early as possible if you want it to make sense.

• As your class consists on a simple dict, there is no or little value in defining it. (In a "real life" scenario, it would be considered as a good practice).

Things got 25% quicker on average starting with 1000 ants.

• You could make your code more concise by using structure to isolate the parts that change.

move_ants() would look like this :

def move_ants(g,point):
x,y = point
for a,b in [(x+1,y),(x,y+1),(x,y-1),(x-1,y)]: # or you could define x generxtor
if (a,b) in g.keys():
g[a,b] += 1
else:
g[a,b] = 1
g[point] -= 4

(Not performance impact)

• In check_status(), instead of iterating on keys and then retrieve the corresponding value, you could use iteritems() :

check_status() would be like this :

def check_status(g):
for k,v in g.iteritems():
if v >= 4:
return k
else: return False

(This does improve performances)

• To get the values from your dict with default values, you could use get(). You'd have something like print(g.get((x,y),0)) and g[a,b] = 1 + g.get((a,b),0). (I really didn't expect so but this made the script more than twice faster).

At the end, my script is like this (I've changed other details but it's mostly personal preferences) :

#!/usr/bin/python

import sys
import time

start = time.time()

##_no_of_ants, _no_of_queries = (input().split())
##no_of_ants = int(_no_of_ants)
##no_of_queries = int(_no_of_queries)

no_of_ants = 1000
no_of_queries = 1

def move_ants(g,point):
x,y = point
for a,b in [(x+1,y),(x,y+1),(x,y-1),(x-1,y)]: # or you could define x generxtor
g[a,b] = 1 + g.get((a,b),0)
g[point] -= 4

def check_status(g):
for k,v in g.iteritems():
if v >= 4:
return k
else: return False

g = {(0,0) : no_of_ants} # or you could use default dict
point = check_status(g)
while point:
move_ants(g,point)
point = check_status(g)
print("Sec:{}".format(time.time()-start))
for q in xrange(no_of_queries):
###_x,_y = input().split()
###x = int(_x)
###y = int(_y)
x,y=1,1
print(g.get((x,y),0))

• It would worthy to mention that your code is in Python 2.x. Thanks for response :) – Vivek Rai Jun 23 '13 at 19:49
• The g[a,b] = 1 + g.get((a,b),0) is already nice, but still a double dict access. The prototypical tip here is to benchmark also using either setdefault() or collections.defaultdict(). – user2512319 Jun 24 '13 at 4:53
• user2512319 : setdefault is what I wanted to do as well but I couldn't make it work with integers. As for defaultdict i considered it as an option (cf comment in the code) and then forgot about it. – SylvainD Jun 24 '13 at 7:11


text:
# Survival probability and local density of states for one-dimensional Hamiltonian systems Academic Article

•
• Overview
•
• Research
•
•
• View All
•

### abstract

• For chaotic systems there is a theory for the decay of the survival probability, and for the parametric dependence of the local density of states. This theory leads to the distinction between "perturbative" and "non-perturbative" regimes, and to the observation that semiclassical tools are useful in the latter case. We discuss what is "left" from this theory in the case of one-dimensional systems. We demonstrate that the remarkably accurate {\em uniform} semiclassical approximation captures the physics of {\em all} the different regimes, though it cannot take into account the effect of strong localization. Comment: 17 pages, 2 figures, textual improvements

### publication date

• January 1, 2003


text:
FAQ/eorder - CBU statistics Wiki
location: FAQ / eorder

Quick formula for the expected value of a Normal order statistic

The expected value of the i-th Normal Order Statistic from a sample of size, n, may be computed as the absolute value of

$$\Phi^{-1}(U(i,n))$$

where $$\Phi^{-1}$$ is the inverse Normal cumulative density function which converts a probability, such as U(i,n), to a z-score.

where the U(i,n) are the U(i) taken from here and reproduced in the table below.

•  U(i,n) i $$1- 0.5^{1/n} i=1$$\frac{i-0.3175}{n+0.365}i=2, \ldots, n-10.5^{1/n} i=n

For example U(1,3)=0.82 (using above approximation) compared to an exact value of 0.85.

An exact version written in the C language programming language (which may be run on Unix) is obtained using a version of Algorithm AS 177 of the Royal Statistical Applied Statistics algorithm page. The C program code is listed here.

The algorithm is labelled Expected Normal Order Statistics (Exact and Approximate) and is based on the original FORTRAN code by Royston, 1982.

A table of expected values of normal order statistics (2.4(a)) are in Neave HR (1978).

References

Neave HR (1978) Statistics tables for mathematicians, engineers, economists and the behavioural and management sciences. Unwin Hyman:London.

Royston, JP (1982), Algorithm AS 177, Applied Statistics, 31(2):161-165.

None: FAQ/eorder (last edited 2013-03-08 10:17:56 by localhost)


text:
# A detail in Rădulescu's Theorem proof

I've been following one Rădulescu's Theorem proof ($G$ is hyperlinear if and only if $\mathcal{L}_{G}$ can be embedded in a ultrapower of the hyperfinite type-$II_{1}$ factor $\mathcal{R}$, where $\mathcal{L}_{G}$ denotes the von Neumann group algebra). I am, however, stuck in a detail that appears to be trivial, since it is not specified in any article I'm reading. So you'll excuse me if this question is quite trivial, but I've been just learning this by myself, out of interest.

Here it goes : Why is it that given a group monomorphism $\Phi : G\rightarrow \mathcal{R}^{\mathcal{U}}$, where $\mathcal{U}$ is an ultrafilter in $\mathbb{N}$ and such that $\tau(\Phi(g))=0$, for every $g\in G\setminus{1_{G}}$ - where $\tau$ denotes the trace - can be extended to a von Neumann algebra embedding $\mathcal{L}_{G}\rightarrow \mathcal{R}^{\mathcal{U}}$? Thank you for the attention !

The conditions guarantee that the linear extension of $\Phi$ is an isometry in the $2$-norm. Indeed, $$\left\|\Phi\left(\sum_k\alpha_k\,g_k\right)\right\|_2^2=\left\|\sum_k\alpha_k\Phi(g_k)\right\|_2^2=\tau_{\mathcal U}\left(\sum_{k,j}\overline{\alpha_j}\alpha_kg_j^{-1}g_k\right) =\sum_{k,j}\overline{\alpha_j}\alpha_j\tau_{\mathcal U}(g_j^{-1}g_k)\\ =\sum_k|\alpha_k|^2=\left\|\sum_k\alpha_k\,g_k\right\|_2^2.$$ Any II$_1$-factor is closed in the 2-norm topology, so the above isometry guarantees the embedding. Interestingly, once you deduce that it is an embedding, it is automatically norm-isometric.


text:
# In a fraction ,twice the numerator is two more than the denominator. if 3 is added to the numerator and denominator each , then the resultant fraction will be 2/3. what was the original fraction

### Other questions on the subject: Math

Math, 18.08.2019 08:00, Simrankanojia
3. two opposite angles of a parallelogram are 6x-17° and x + 63º. find the measure of each angle of theparallelogram.
Math, 18.08.2019 11:00, Vsinghvi
Find d(d, t) if co ordinate of t and d are x=-4 and y=7 respesctively
Math, 19.08.2019 10:00, jack626259
2. the average of two consecutive even numbers is 109 and the average oftwo consecutive odd numbers is 114. if the smaller odd number is 3 greaterthan the larger even number then what is the sum of the smaller odd numberand the larger even number.


text:
# zbMATH — the first resource for mathematics

The stability theorem for smooth pseudoisotopies. (English) Zbl 0691.57011
The purpose of this very long paper is to prove the pseudoisotopy stability theorem in the smooth category. More precisely, if $${\mathcal C}(M)$$ denotes the space of self-diffeomorphisms of $$M\times I$$, which restrict to the identity on $$M\times O\cup \partial M\times I$$, carrying the weak smooth topology, then the suspension map from $${\mathcal C}(M)$$ to $${\mathcal C}(M\times I)$$ is k-connected under (for example) the numerical conditions $$k\geq 4$$ and dim $$M\geq 3k+4$$. Hence in relatively low dimensions the homotopy of $${\mathcal C}(M)$$ can be studied in terms of the homotopy of the infinite loop space $${\mathbb{P}}(M)=\lim_{m\to \infty}{\mathcal C}(M\times I^ m)$$, itself closely related to Waldhausen’s geometric K- group A(M). I will discuss what seem to me to be limitations of these results in a final paragraph, but first I wish to give some account of the methods and results, which I hope will be intelligible to the non- specialist. Official health warning: the author has made every effort to be accurate in his details, but this area is notorious for technical problems arising in the published arguments. The main tools are adapted from the parametrized Morse theory of J. Cerf, in which one defines a Morse function on the total space of a bundle of manifolds parametrized by points of the base B, and A. Hatcher’s handle exchange theorem, which under certain conditions allows the exchange of i- for $$(i+2)$$-handles. Stated in this generality, this pair of results can be combined to give a heuristic proof of the stability theorem - in the present paper, as the author makes clear, only those lemmas are proved which are necessary for the main theorem. For the sake of simplicity consider the argument for the closed disc $$D^ n.$$
The space of all submanifolds of $${\mathbb{R}}^ n$$ diffeomorphic to $$D^ n$$ is a model for the classifying space B$${\mathcal C}(D^{n-1})$$, and may be studied via the space $$\tilde {\mathcal H}^ h({\mathbb{R}}^ n)$$ of all pairs (*$$\simeq V,h)$$, V being a compact contractible n-submanifold of $${\mathbb{R}}^ n$$ and h: $$V\to [0,]$$ a function of generalized Morse type. This last condition means that $$h^{-1}()=\partial V$$ and h has only Morse and birth-death singularities (modulo local renormalization in some neighbourhood for the latter type h has the form $$y^ 3_ 1+Q(y_ 2,...,y_ n))$$. The k-connectivity of the suspension for $${\mathcal C}(D^{n-1})$$ is now equivalent to the k-connectivity of a compatible “suspension” from $$\tilde {\mathcal H}^ h({\mathbb{R}}^ n)\to \tilde {\mathcal H}^ h({\mathbb{R}}^{n+1})$$. Assuming that $$k\sim n/3$$, $$\tilde {\mathcal H}^ h$$ can be replaced by its subspace $${\mathcal H}^ h_{k+2,k+3}$$ consisting of pairs (*$$\simeq V,h)$$, where h has one non-degenerate critical point of index 0, and all other critical points are either non-degenerate of index $$k+2$$ or $$k+3$$, or birth-death points of index $$(=index$$ Q) $$k+2$$. This is a smooth version of Hatcher’s two index theorem, and receives a detailed proof in Chapter VI (80 pages). Intuitively k-connectivity of the suspension now follows because the approximating space is equivalent to the space of contractible cell-complexes consisting of $$(k+2)$$ and $$(k+3)$$-cells attached to a single 0-cell with the attaching maps for each cell well-defined up to rotation. However the technical proof uses properties of stratified sets, which are carefully discussed in Chapter III (62 pages).
I have already mentioned that the stability theorem forms part of the programme of studying the homotopy type of the space $${\mathcal C}(M)$$ by means of K-theory. This translation of problems of simple homotopy type to questions of homotopy in a classifying space is certainly elegant, but seems to offer no more than limited help in solving specific geometric problems. For example let $$C_ p$$ be a cyclic group of prime order acting freely on $$S^ 3$$- then using the homotopy equivalence $$SO(4)\simeq SDiff(S^ 3)$$ and the unstable theory of maps between classifying spaces, one can show that the action is homotopically equivalent to a specific free linear action. At least if the action extends to $$C_{2p}$$ there is some geometric evidence that the homotopy above is actually simple, and it would be nice to be able to prove this using (say) some variant of the Waldhausen functor A( ). However any evidence provided by this method would appear at best to be stable, that is, one would not obtain the specific representation provided in the more elementary theory by $$[BC_ p,BSO(4)]$$. And stably the problem of characterizing allowable Reidemeister torsions is much easier - thus if the $$C_ p$$ action embeds in a $$C_ pt$$ action for arbitrarily large values of t, the associated Reidemeister torsion must be linear. (Intuitively this follows because we are approximating a free SO(2)- action, and these are covered by the theory of Seifert fibrations). As a mathematician interested in low-dimensional geometric problems of this kind, I am therefore left hoping that this elaborately constructed machine will eventually be sufficiently well-understood to provide real help.
Reviewer: Ch.Thomas

##### MSC:
 57R50 Differential topological aspects of diffeomorphisms 18F25 Algebraic $$K$$-theory and $$L$$-theory (category-theoretic aspects) 57R70 Critical points and critical submanifolds in differential topology 57R65 Surgery and handlebodies
Full Text:


text:
# Code Samples - Neevia PDFcompress

## Example 1: Compress a PDF file (high image quality, low compression) - ASP.NET

In order to compress PDF files from ASP.NET you need to make sure that Neevia PDF compress is installed on your Windows machine. After that copy the PDFcompress .NET assembly from the C:\Program files (x86)\neeviaPDF.com\PDFcompress\dotNet\ folder into your website bin folder and use the code below. It will compress your file while preserving the image quality.

Scroll down for the C# samples

### Visual Basic Copy

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36  <%@ Page Language="VB" %>

### VC# Copy

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38  <%@ Page Language="C#" %>


text:
# Subsection2.1Modal Operations

To discuss the Higher Order SVD, we must first have a general understanding of two modal operations, modal unfoldings and modal products.

##### Definition2.1Modal Unfolding
Suppose $\mathcal{A}$ is a 3rd-order tensor and $\mathcal{A} \in \mathbb{R}^{n_1 \times n_2 \times n_3}$. Then the modal unfolding $\mathcal{A}_{(k)}$ is the matrix $\mathcal{A}_{(k)} \in \mathbb{R}^{n_k \times N}$ where $N$ is the product of the two dimensions unequal to $n_k$.

For a 3rd-order tensor, $\mathcal{A} \in \mathbb{R}^{n_1 \times n_2 \times n_3}$, there are 3 modal unfoldings and in general a $d$-order tensor has $d$ modal unfoldings. As a simple example the modal unfoldings for $\mathcal{A} \in \mathbb{R}^{3 \times 4 \times 2}$ are shown below, where $\mathcal{A}_1$ and $\mathcal{A}_2$ are the frontal slices of $\mathcal{A}$. $\mathcal{A}_1 = \begin{bmatrix} 1 & 2 & 3 & 4\\ 5 & 6 & 7 & 8\\ 9 & 10 & 11 & 12 \end{bmatrix} \quad \mathcal{A}_2 = \begin{bmatrix} 13 & 14 & 15 & 16\\ 17 & 18 & 19 & 20\\ 21 & 22 & 23 & 24 \end{bmatrix}$ $\mathcal{A}_{(1)} = \begin{bmatrix} 1 & 2 & 3 & 4 & 13 & 14 & 15 & 16\\ 5 & 6 & 7 & 8 & 17 & 18 & 19 & 20\\ 9 & 10 & 11 & 12 & 21 & 22 & 23 & 24 \end{bmatrix}$ $\mathcal{A}_{(2)} = \begin{bmatrix} 1 & 5 & 9 & 13 & 17 & 21\\ 2 & 6 & 10 & 14 & 18 & 22\\ 3 & 7 & 11 & 15 & 19 & 23\\ 4 & 8 & 12 & 16 & 20 & 24 & \end{bmatrix}$ $\mathcal{A}_{(3)} = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \end{bmatrix}$

Using the definition of modal unfolding we can now define a modal product between a matrix and a tensor.

##### Definition2.2Modal Product
The modal product, denoted $\times_{k}$, of a 3rd-order tensor $\mathcal{A} \in \mathbb{R}^{n_1 \times n_2 \times n_3}$ and a matrix $\textbf{U} \in \mathbb{R}^{J \times n_k}$, where $J$ is any integer, is the product of modal unfolding $\mathcal{A}_{(k)}$ with $\textbf{U}$. Such that $\textbf{B}=\textbf{U} \mathcal{A}_{(k)} = \mathcal{A} \times_{k} \textbf{U}$

These two operations will be used to generalize the standard SVD definition.

# Subsection2.2Higher Order SVD (HOSVD)

Informally the Higher Order SVD is simply defined as an SVD for each of the tensors modal unfoldings.

##### Definition2.3Higher Order SVD
Suppose $\mathcal{A}$ is a 3rd-order tensor and $\mathcal{A} \in \mathbb{R}^{n_1 \times n_2 \times n_3}$. Then there exists a Higher Order SVD such that $\textbf{U}^{T}_{k}\mathcal{A}_{(k)}=\Sigma_{k} \textbf{V}^{T}_{k} \quad (1\leq k \leq d)$ where $\textbf{U}_{k}$ and $\textbf{V}_{k}$ are unitary matrices and the matrix $\Sigma_{k}$ contains the singular values of $\mathcal{A}_{(k)}$ on the diagonal, $[\Sigma_{k}]_{ij}$ where $i=j$, and is zero elsewhere.

Using this definition, computing an HOSVD for a tensor of order-$N$ is only as computationally difficult as performing $N$ matrix SVD's. In practice the SVD of a matrix is useful in compressing a matrix to a representation that is arbitrarily close to the original. Generalizing this to the higher order tensor case can be accomplished by using the unitary matrices $U_k$ from the HOSVD to find a tensor $\mathcal{S}$ as follows: (the $\rightarrow$ is used to denote undoing a modal unfolding) \begin{align*} \textbf{U}^{T}_{1} \mathcal{A}_{(1)} &= \hat{\mathcal{A}}_{(1)} \rightarrow \hat{\mathcal{A}}\\ \textbf{U}^{T}_{2} \hat{\mathcal{A}}_{(2)} & = \hat{\hat{\mathcal{A}}}_{(2)} \rightarrow \hat{\hat{\mathcal{A}}}\\ \textbf{U}^{T}_{3} \hat{\hat{\mathcal{A}}}_{(3)} &= \mathcal{S}_{(3)} \rightarrow \mathcal{S} \end{align*} This can be denoted by sequential modal products much more concisely. \begin{align*} \mathcal{S} &=\mathcal{A}\times_1 U^{T}_{1} \times_2 U^{T}_{2} \times_3 U^{T}_{3}\\ \mathcal{A} &=\mathcal{S}\times_1 U_{1} \times_2 U_{2} \times_3 U_{3} \end{align*}

This $\mathcal{S}$ tensor is referred to as the core tensor. While this tensor is not diagonal the entries tend to decrease as distance from the diagonal increases where the diagonal is the entries from the upper left hand corner of the cube to the lower right hand corner. This property is useful when compressing the original $\mathcal{A}$ because the dimension of $U$ can be reduced by dropping the smaller terms, and a close approximation will still be generated, much like the compression of a matrix using SVD. The biggest example of this is the compression of color photos where each frontal slice corresponds to intensities of red, green, or blue instead of the matrix example where entries correspond to intensities on the gray-scale. This approach could also be used to first compress a tensor, then perform a CP decomposition on the compressed tensor to save computational resources.

# Subsection2.3Rank of Higher Order Tensors

The notion of rank with respect to higher order tensors is not as simple as the rank of a matrix.

##### Definition2.4Rank of a Tensor
The rank of a tensor$\mathcal{A}$ is the smallest number of rank 1 tensors that sum to $\mathcal{A}$.

This definition of rank comes up naturally within many of the common tensor decompositions. For example, in the CANDECOMP/PARAFAC (CP) decomposition the rank specifies the minimum number of vector outer products required to reproduce the tensor exactly. And, with a somewhat circular claim, an exact CP decomposition with minimal vector outer products can be used to determine the rank of a tensor, this is also referred to as a rank decomposition. While the definition for matrix rank is an analog to tensor rank, the properties are quite different. For example, there is no general algorithm to determine the rank of a given higher order tensor. There is only a loose upper bound on the rank of a 3rd-order tensor, $\mathcal{A}\in\mathbb{R}^{I\times J\times K}$, described by $rank(\mathcal{A})\leq \mbox{min}\{IJ,IK,JK\}$, but the rank is often lower than this for randomly generated tensors [4.7].

# Subsection2.4CANDECOMP/PARAFAC Decomposition

Unfortunately there is no single algorithm to perform a CP decomposition on any tensor. This is partially due to the fact that the rank of a higher order tensor is not known precisely until a CP decomposition has been performed and is known to be the most concise decomposition.

##### Definition2.5CP Decomposition
A CP decomposition of a 3rd-order tensor, $\mathcal{A}$, is defined as a sum of vector outer products, denoted $\circ$, that equal or approximately equal $\mathcal{A}$. For $R = rank(\mathcal{A})$$\mathcal{A} = \sum_{r=1}^{R}a_r \circ b_r \circ c_r$ and for $R \lt rank(\mathcal{A})$$\mathcal{A} \approx \sum_{r=1}^{R}a_r \circ b_r \circ c_r$

The CP decomposition is nicely visualized by Kolda and Bader (2009) in Figure 3.1.

The vectors of a CP composition, $a_r$, $b_r$, and $c_r$ for $1 \leq r \leq R$, are often compiled into the columns of the matrices $\textbf{A}$, $\textbf{B}$, and $\textbf{C}$ respectively, and the CP decomposition is written more concisely, $\mathcal{A}=[[\textbf{A},\textbf{B},\textbf{C}]]$. This type of matrix multiplication is often denoted by the $\odot$ symbol. For instance, $\textbf{A} \odot \textbf{B} = [a_1|a_2|\dots|a_n] \odot [b_1|b_2|\dots|b_n] = [a_1 \circ b_1|a_2 \circ b_2|\dots|a_n \circ b_n]$ The example below, from Bader and Kolda (2009), demonstrates why the rank of a matrix is difficult to determine precisely. In this example a CP decomposition over the real and complex fields is performed for $\mathcal{A} \in \mathbb{R}^{2 \times 2 \times 2}$ where $\mathcal{A}_1$ and $\mathcal{A}_2$ are the frontal slices of $\mathcal{A}$ [4.3].

\begin{align*} \mathcal{A}_1 &= \begin{bmatrix} 1 & 0\\0 & 1 \end{bmatrix} &\mathcal{A}_2 &= \begin{bmatrix} 0 & 1\\-1 & 0 \end{bmatrix} \end{align*}

The rank decomposition over $\mathbb{R}$ is $\mathcal{A}= [[\textbf{A},\textbf{B},\textbf{C}]]$, where \begin{align*} \textbf{A}&=\begin{bmatrix} 1 & 0 & 1\\0 & 1 & -1\end{bmatrix} & \textbf{B}&=\begin{bmatrix} 1 & 0 & 1\\0 & 1 & 1\end{bmatrix} & \textbf{C} &= \begin{bmatrix} 1 & 1 & 0\\-1 & 1 & 1\end{bmatrix} \end{align*} but over $\mathbb{C}$ \begin{align*} \textbf{A}&=\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1\\-i & i \end{bmatrix} & \textbf{B}&=\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1\\i & -i \end{bmatrix} & \textbf{C}&=\begin{bmatrix} 1 & 1\\i & -i \end{bmatrix}. \end{align*}

This leads to a very surprising property, the rank of a tensor can be different over $\mathbb{R}$ and $\mathbb{C}$. For this reason I have restricted the definitions to $\mathbb{R}$ to remove this ambiguity.

Performing a CP decomposition on a 3rd order tensor $\mathcal{A}$ is a matter of performing a Alternating Least Squares (ALS) routine to minimize $||\mathcal{A}_{(1)} - \textbf{A}(\textbf{C}\odot \textbf{B})^T||$. To perform an ALS routine on this system, the system is divided into 3 standard least squares problems where 2 of the 3 matrices are held constant and the third is solved for. The main problem in implementing an ALS routine such as this, is choosing initial values for the two matrices that are held constant to initialize the first least squares problem. This method may take many iterations to converge, the point of convergence is heavily reliant on the initial guess, and the computed solution is not always accurate. Faber, Bro, and Hopke (2003) investigated six methods as an alternative to the ALS method and none of them came out more effective than ALS in terms of accuracy of solution, but some did converge faster [4.6]. In addition, derivative methods have been developed that are superior to the ALS method in terms of convergence and solution accuracy but are much more computationally expensive [4.3]. For quantum mechanical problems involving a few $3 \times 3 \times 3$ tensors accuracy is paramount to computational expense. One such algorithm is the PMF3 algorithm described in Paatero (1997) which computes changes to all three matrices simultaneously. This allows for faster convergence than the ALS method and optional specificity for non-negative solutions reduces divergence in systems that are known to have positive solutions [4.5].


text:
Dataflow Programming:…

From the post:

Because the dataflow operators in a graph work in parallel, the model allows overlapping I/O operations with computation. This is a “whole application” approach to parallelization as opposed to many thread-oriented performance frameworks that focus on hot sections of code such as for loops. This addresses a key problem in processing “big data” for today’s many-core processors: feeding data fast enough to the processors.

While dataflow does this, it scales down easily as well. This distinguishes it from technologies, such as Hadoop and to a lesser extent, Map Reduce, which don’t scale downward well due to their innate complexity.

We’ve discussed how a dataflow architecture exploits multicore. These same principles can be applied to multi-node clusters by extending dataflow queues over networks with a dataflow graph executed on multiple systems in parallel. The compositional model of building dataflow graphs allows for replication of pieces of the graph across multiple nodes. Scaling out extends the reach of dataflow to solve large data problems.

Read the first comment. By J.P. Morrison, author of Flow Based Programming, the inspiration for Pipes. (Shamelessly repeated from a post by Marko Rodriguez on the gremlin-users list, Achim first noticed the article.)

Be aware that Amazon lists the Kindle edition for \$29.00 and a hardback edition for \$69.00. Sadly one reader reports the book has no index?

3 Responses to “Dataflow Programming:…”

1. […] like DataFlow Programming… or Flow-Based Programming (FBP) to me. In which case the claim that: It’s just Java. Crunch […]

2. Paul Morrison says:

Hi guys! Just wanted to say that the first version of the 2nd Edition of Flow-Based Programming indeed didn’t have an index. Ernesto Compatangelo contacted me to say that his version of the book had lots of those little plastic stickies stuck in it, so I promptly asked him to send me a list of them – which he kindly did. So there is now an index! I think the ebook versions all have indices, but if there are some early buyers of the paperback that need an index, maybe we could work something out … 🙂

3. Patrick Durusau says:

Excellent! I have written to Amazon to see if the index appears in a later printing. Looking forward to reading it!


text:
Another relationship of variables

1. Jul 31, 2005

eNathan

Yet again, im programming a software to align pictures on a 2D plane, kinda like they are in windows exploror. I need to find a relationship betwen these.

I C R
_______
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
6 1 1
7 2 2
8 2 3
9 2 4
10 2 5
11 3 1

I would be my for loop counter, C would be the colum of picture I, and R would be what row it belongs to.

C = Ceil(i / 5);
And I have come close to finding the value of R, so far I have
R = i - (Floor(i/(5 + C))*5);
But I know the latter equation is wrong, I just cant seem to figure it out out.

2. Jul 31, 2005

VietDao29

Are you sure 6 1 1??? I think it should read 6 2 1.
C = [(I - 1) / 5] + 1. Where [...] is a function that takes the integer part before the decimal point of a real number. Ex : [1.5] = 1.
In some programming languages, you can write it as : C = Int((I - 1) / 5) + 1.
R = I - (C - 1) * 5.
Viet Dao,

Last edited: Jul 31, 2005
3. Jul 31, 2005

eNathan

Oh my :surprised It was soooo simple! I am speechless. Of course, just subtract from I, 5 C abount of times (and add one of course).

Thank you very much.


text:
1. Mar 17, 2010

TimH

I'm teaching myself QM and have a question about a problem in my text. (If this makes it homework, sorry to post in the wrong forum).

Basically the question is about three observables A,B,C. They obey the following rules:

[A,B]=0, [A,C]=0, but [B,C] not equal to 0.

So this is like the situation with the total squared angular momentum L^2 and the axial angular momenta Lx, Ly, Lz. Now I know that if the observables commute, they "share a complete set of eigenstates." So in this situation you can have eigenstates of A that are also eigenstates of B or C, but not both at the same time [yes?]. So you can't have a single quantum state that is an eigenstate of all three [yes?]. Now the question asks about the effects of these relations on sequential measurements of the observables. If you start in an A eigenstate, and measure B or C, could the state be left unchanged since they both "contribute" eigenstates to A? If you start in B or C and measure the other, will you get an even spread across the available eigenstates since they don't commute?

Or, am I drifting hopelessly in Hilbert Space??

2. Mar 17, 2010

elibj123

starting with an A's eigenstate and measuring B and C will never change the eigenstate, since the state is an eigenstate of B and C as well (as you pointed out) therefore has a definite eigenvalue (which will be measured with 100% probabillity).

But the eigenstates of B are not eigenstates of C (again, as you pointed out)- that doesn't necesarilly means that an eigenstate of B is uniformly superpositioned from eigenstates of C. I mean, an eigenstate of B can be much more closer to one eigenstate of C and not the other. F.e.:

$$|B_{1}>=\frac{\sqrt{3}}{2}|C_{1}>+\frac{1}{2}|C_{2}>$$

Perhaps the commutation property [A,B]=0,[B,C]=0 does tell that its spread uniformly, but it's not observed easily. In the general case, there is no restriction on how eigenstates are expressed in terms of other operator's eigenstates.

3. Mar 17, 2010

TimH

Okay, thank you for that. I wondered if [B,C] not equaling zero made it a straight 50-50 coin flip or not.

Now I'm definitely a beginner at QM, I'm trying to get the overall structure (I'm reading a good text, Essential Quantum Mechanics by Bowman). So in the above situation A's eigenstates (which are e.g. just eigenvectors in a matrix representation), form a complete set that spans the space (since A is an observable=Hermitian). And these are the same as B's and C', since it commutes with them. But then how can B's not be C's? I'm probably missing something basic...

4. Mar 17, 2010

Matterwave

I believe commutation being zero only says that the two observables may share eigenstates. I have never seen a proof that they must share eigenstates or that their eigenstates must be the same. If two observables don't commute, then they literally cannot share eigenstates.

Again, just because I've never seen a proof that commutative observables must share eigenstates, doesn't mean that no such proof exists. I may be wrong on this.

5. Mar 17, 2010

TimH

Okay, my text says "If F,G share a complete set of eigenstates, then [F,G] vanishes," where "complete set" means a set of vectors that are linearly independent and span the space (i.e. a basis). I thought that since observables are Hermitian and therefore have a complete set, there was just one such complete set for each observable (i.e. its eigenvectors in the matrix representation). Now with angular momentum for example, Lz and L^2 commute, and therefore share eigenstates. But L^2 also has eigenstates with Lx and Ly. So its like L^2 has three distinct sets of eigenstates. So are these sets all complete?

6. Mar 17, 2010

Matterwave

Well, it's certainly true that "If F,G share a complete set of eigenstates, then [F,G] vanishes"; however, does your book mention anything to the converse? "If [F,G] vanishes, then F,G share a complete set of eigenstates"?

7. Mar 17, 2010

SpectraCat

Yes, but it is probably more correct to say that L^2 has a complete set of eigenstates that can be expressed in the basis of one of the other 3 operators, say Lz. The eigenstates of the remaining operators (Lx & y), can then be expressed as linear combinations in the Lz eigenbasis. Each of these linear combinations is of course also an eigenstate of L2, however, they are not *new* eigenstates ... they are degenerate states that are non-orthogonal to the Lz basis by definition, since they are expressed as linear combinations of these states.

Thus, just as in the Stern-Gerlach experiment, you are free to choose one spatial axis to define eigenstates of the projection of angular momentum. If you then try to measure the projection of angular momentum on any other axis for one of these states, you will find the system in a superposition (i.e. not an eigenstate).


text:
# Zabir said I must write a letter- change the narration

Zabir said that he might write a letter

zabir told that he should write a letter

Zabir told that he must write a letter

Zabir said that he had to write a letter

প্রশ্নের বর্ণনাঃ শীঘ্রই আসছে...


text:
# Does torch.cat work with backpropagation?

I was wondering if it was okay to use torch.cat within my forward function. I am doing so because I want the first two columns of my input to skip the middle hidden layers and go directly to the final layer.

Here is my code: you can see that I use torch.cat at the last moment to make xcat.

Does the gradient propagate back? or does the torch.cat cover up what happened to my hidden variables?

class LinearRegressionForce(nn.Module):

def __init__(self, focus_input_size, rest_input_size, hidden_size_1, hidden_size_2, output_size):
super(LinearRegressionForce, self).__init__()

self.in1 = nn.Linear(rest_input_size, hidden_size_1)
self.middle1 = nn.Linear(hidden_size_1,hidden_size_2)
self.out4 = nn.Linear(focus_input_size + hidden_size_2,output_size)

def forward(self, inputs):
focus_inputs = inputs[:,0:focus_input_size]
rest_inputs = inputs[:,focus_input_size:(rest_input_size+focus_input_size)]
x = self.in1(rest_inputs).clamp(min=0)
x = self.middle1(x).clamp(min=0)
xcat = torch.cat((focus_inputs,x),1)
out = self.out4(xcat).clamp(min=0)
return out

I call it like so:

rest_inputs = Variable(torch.from_numpy(rest_x_train))
focus_x_train_ones = np.concatenate((focus_x_train, np.ones((n,1))), axis=1)
focus_inputs =  Variable(torch.from_numpy(focus_x_train_ones)).float()
inputs = torch.cat((focus_inputs,rest_inputs),1)

predicted = model(inputs).data.numpy()

Yes, torch.cat works with backward operation.


text:
# Proving the Kronecker Weber Theorem for Quadratic Extensions

I am starting to read about the Kronecker-Weber Theorem. It says that any abelian extension of $\mathbb{Q}$ is contained in a cyclotomic extension. I read somewhere that for quadratic extensions the proof is not very difficult.

Can anyone tell me any reference material for the proof of the kronecker weber theorem for quadratic extensions ?

• For a prime $p$ the field $\Bbb{Q}(\zeta_p)$ contains $\sqrt{p^*}$, where $p^*=(-1)^{(p-1)/2}p$. This gets you started. For example you always find $\sqrt p$ inside $\Bbb{Q}(\zeta_p,i)=\Bbb{Q}(\zeta_{4p})$. With composites, just compose the fields. – Jyrki Lahtonen Nov 8 '16 at 5:48
• Possible duplicate of Square roots of integers and cyclotomic fields – Watson Nov 8 '16 at 7:45
• @Watson: I don't see any "reference material" linked to in your suggestion? – Willie Wong Nov 9 '16 at 1:11
• @WillieWong : I retracted my close vote. – Watson Nov 9 '16 at 15:51

Look up Gauss sums. They express $\sqrt{p}$ as a function of roots of unity. They occur in Gauss's fourth proof of quadratic reciprocity. The classic textbook by Ireland and Rosen "A classical introduction to modern number theory" has extensive discussion of them and their generalisations. Gauss sums are really just Lagrange resolvents for the cyclotomic equation. Lang's book "Algebraic Number Theory" also explains conceptually the relation between reciprocity and the fact that quadratic fields are subfields of cyclotomic fields. Weber's original proof used this as one of his cases.


text:
Scheduling on identical machines: How good is LPT in an on-line setting?(English)Zbl 0892.90098

Summary: We consider a parallel machine scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on $$m$$ identical machines, where preemption is not allowed and the number of jobs is unknown in advance. Each job becomes available at its release date, which is not known in advance, and its processing time becomes known at its arrival. We deal with the problem of minimizing the makespan, which is the time by which all jobs have been finished. We propose and analyze the following on-line LPT algorithm: At any time a machine becomes available for processing, schedule an available job with the largest processing time. We prove that this algorithm has a performance guarantee of $${3\over 2}$$, and that this bound is tight. Furthermore, we show that any on-line algorithm will have a performance bound of at least 1.3473. This bound is improved to $$(5- \sqrt 5)/2\approx 1.3820$$ for $$m=2$$.

MSC:

 90B35 Deterministic scheduling theory in operations research
Full Text:

References:

 [1] Graham, R. L., Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math., 17, 416-429 (1969) · Zbl 0188.23101 [2] Hall, L. A.; Shmoys, D. B., Approximation schemes for constrained scheduling problems, (Proc. 30th Ann. IEEE Symp. on Foundations of Computer Science (1989), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA), 134-139 [3] Hong, K. S.; Leung, J. Y.-T., On-line scheduling of real-time tasks, IEEE Trans. Comput., 41, 1326-1331 (1992) [5] Shmoys, D. B.; Wein, J.; Williamson, D. P., Scheduling parallel machines on-line, SIAM J. Comput., 24, 1313-1331 (1995) · Zbl 0845.68042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
# Eisenstein Series and Bernoulli Numbers¶

We introduce generalized Bernoulli numbers attached to Dirichlet characters and give an algorithm to enumerate the Eisenstein series in .

## The Eisenstein Subspace¶

Let be the space of modular forms of weight for , and let be the Hecke algebra acting on , which is the subring of generated by all Hecke operators. Then there is a -module decomposition

where is the subspace of modular forms that vanish at all cusps and is the Eisenstein subspace, which is uniquely determined by this decomposition. The above decomposition induces a decomposition of and of , for any Dirichlet character of modulus .

## Generalized Bernoulli Numbers¶

Suppose is a Dirichlet character of modulus over . Leopoldt [Leo58] defined generalized Bernoulli numbers attached to .

Definition 5.1

We define the generalized Bernoulli numbers attached to by the following identity of infinite series:

If is the trivial character of modulus and are as in Section Examples of Modular Forms of Level 1, then , except when , in which case (see Exercise 5.2).

### Algebraically Computing Generalized Bernoulli Numbers¶

Let denote the field generated by the image of the character ; thus is the cyclotomic extension , where is the order of .

Algorithm 5.2

Given an integer and any Dirichlet character with modulus , this algorithm computes the generalized Bernoulli numbers , for .

1. Compute to precision by computing to precision and computing the inverse , then multiplying by .

2. For each , compute , to precision . This requires computing to precision . (Omit computation of if since then .)

3. Then for , we have

where is the coefficient of in .

Note that in steps (1) and (2) we compute the power series doing arithmetic only in , not in , which could be much less efficient if has large order. In step (1) if is huge, we could compute the inverse using asymptotically fast arithmetic and Newton iteration.

Example 5.3

The nontrivial character with modulus has order and takes values in . The Bernoulli numbers for even are all and for odd they are

Example 5.4

The generalized Bernoulli numbers need not be in . Suppose is the mod character such that . Then for even and

Example 5.5

We use Sage to compute some of the above generalized Bernoulli numbers. First we define the character and verify that (note that in Sage zeta4 is ).

sage: G = DirichletGroup(5)
sage: e = G.0
sage: e(2)
zeta4

We compute the Bernoulli number .

sage: e.bernoulli(1)
-1/5*zeta4 - 3/5

We compute .

sage: e.bernoulli(9)
-108846/5*zeta4 - 176868/5

Proposition 5.6

If and , then .

Proof

See Exercise 5.3.

### Computing Generalized Bernoulli Numbers Analytically¶

This section, which was written jointly with Kevin McGown, is about a way to compute generalized Bernoulli numbers, which is similar to the algorithm in Section Fast Computation of Bernoulli Numbers.

Let be a primitive Dirichlet character modulo its conductor . Note from the definition of Bernoulli numbers that if , then

(1)

For any character , we define the Gauss sum as

where is the principal root of unity. The Dirichlet -function for for is

In the right half plane this function is analytic, and because is multiplicative, we have the Euler product representation

(2)

We note (but will not use) that through analytic continuation can be extended to a meromorphic function on the entire complex plane.

If is a nonprincipal primitive Dirichlet character of conductor such that , then (see, e.g., [Wan82])

Solving for the Bernoulli number yields

This allows us to give decimal approximations for . It remains to compute exactly (i.e., as an algebraic integer). To simplify the above expression, we define

and write

(3)

Note that we can compute exactly in the field .

The following result identifies the denominator of .

Theorem 5.7

Let and be as above, and define an integer as follows:

Then is integral.

Proof

See [Car59a] for the proof and [Car59b] for further details.

To compute the algebraic integer , and we compute to very high precision using the Euler product (2) and the formula (3). We carry out the same computation for each of the conjugates of , which by (1) yields the conjugates of . We can then write down the characteristic polynomial of to very high precision and recognize the coefficients as rational integers. Finally, we determine which of the roots of the characteristic polynomial is by approximating them all numerically to high precision and seeing which is closest to our numerical approximation to . The details are similar to what is explained in Section Fast Computation of Bernoulli Numbers.

## Explicit Basis for the Eisenstein Subspace¶

Suppose and are primitive Dirichlet characters with conductors and , respectively. Let

(4)

where

Note that when and , then , where is from Chapter Modular Forms.

Miyake proves statements that imply the following in [Miy89, Ch. 7].

Theorem 5.8

Suppose is a positive integer and , are as above and that is a positive integer such that . Except when and , the power series defines an element of . If , , , and , then is a modular form in .

Theorem 5.9

The Eisenstein series in coming from Theorem 5.8 with and form a basis for the Eisenstein subspace .

Theorem 5.10

The Eisenstein series defined above are eigenforms (i.e., eigenvectors for all Hecke operators ). Also , for , is an eigenform.

Since is normalized so the coefficient of is , the eigenvalue of is the coefficient

of (see Proposition 9.10). Also for with prime, the coefficient of is , for , and .

Algorithm 5.11

Given a weight and a Dirichlet character of modulus , this algorithm computes a basis for the Eisenstein subspace of to precision .

1. [Weight Trivial Character?] If and , output the Eisenstein series , for each divisor with , and then terminate.

1. [Empty Space?] If , output the empty list.
2. [Compute Dirichlet Group] Let be the group of Dirichlet characters with values in , where is the exponent of .
3. [Compute Conductors] Compute the conductor of every element of using Algorithm 4.19.
4. [List Characters ] Form a list of all Dirichlet characters such that divides .
5. [Compute Eisenstein Series] For each character in , let and compute for each divisor of . Here we compute using (4) and Algorithm 5.2.

Remark 5.12

Algorithm 5.11 is what is currently used in Sage. It might be better to first reduce to the prime power case by writing all characters as a product of local characters and combine steps (4) and (5) into a single step that involves orders. However, this might make things more obscure.

Example 5.13

The following is a basis of Eisenstein series for .

We computed it as follows:

sage: E = EisensteinForms(Gamma1(13),2)
sage: E.eisenstein_series()

We can also compute the parameters that define each series:

sage: e = E.eisenstein_series()
sage: for e in E.eisenstein_series():
...       print e.parameters()
...
([1], [1], 13)
([1], [zeta6], 1)
([zeta6], [1], 1)
([1], [zeta6 - 1], 1)
([zeta6 - 1], [1], 1)
([1], [-1], 1)
([-1], [1], 1)
([1], [-zeta6], 1)
([-zeta6], [1], 1)
([1], [-zeta6 + 1], 1)
([-zeta6 + 1], [1], 1)

## Exercises¶

Exercise 5.1

Suppose and are diagonalizable linear transformations of a finite-dimensional vector space over an algebraically closed field and that . Prove there is a basis for so that the matrices of and with respect to that basis are both simultaneously diagonal.

Exercise 5.2

If is the trivial character of modulus and are as in Section Examples of Modular Forms of Level 1, then , except when , in which case .

Exercise 5.3

Prove that for if , then .

Exercise 5.4

Show that the dimension of the Eisenstein subspace is by finding a basis of series . You do not have to write down the -expansions of the series, but you do have to figure out which to use.

#### Previous topic

Dirichlet Characters

#### Next topic

Dimension Formulas


text:
# Theta bound of the following function [duplicate]

Suppose the function $f(n)$ is defined as the number of $\ast$ printed in the following code

for(int i = 0; i<n; i++) {
for(int j = i; j<n; j++) {
for(int k = j + 200; k<2n; k++) {
for( int r = k^2; r<n; r++) {
print(*);
}
}
}
}

I suspect the answer is $\Theta(n^{2.5})$, by running the code at $n=5000$ and $n=50000$, but I do not have a rigid proof.

Can anyone enlighten me? Thank you!

## marked as duplicate by David Richerby, Evil, Raphael♦ algorithms StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Aug 28 '18 at 18:37

• What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? – Raphael Aug 28 '18 at 18:38

First, note that we print a * for every tuple $(i,j,k,r)$ such that $0 \leq i \leq j \leq k-200 \leq \sqrt{r}-200\leq \sqrt{n}-200$
For every $i$ and $j$ there are at most $(\sqrt{n}-200)$ options, for $k$ it is $\sqrt{n}$ and for $r$ it is $n$. Thus the upper bound for the number of * is $(\sqrt{n}-200)\cdot (\sqrt{n}-200) \cdot \sqrt{n} \cdot n\in O(n^{2.5})$.
To compute the lower bound, we can take $i$'s in the range between $0$ and $\frac{\sqrt{0.5n}-200}{2}$, $j's$ between $\frac{\sqrt{0.5n}-200}{2}+1$ and $\sqrt{0.5n}$, $k$'s between $\sqrt{0.5n}+1$ and $\sqrt{0.75n}$, and finally, $r's$ between $0.75n+1$ to $n$. Thus the number of options for a tuple $(i,j,k,r)$ is more than $(\frac{\sqrt{0.5n}-200}{2})^2 \cdot (\sqrt{0.75n}-\sqrt{0.5n})\cdot 0.25n \in \Omega(n^{2.5})$.
Thus the answer is $\Theta(n^{2.5})$


text:
# Add-On Index Page Throwing Parse Error That Is Not Correct

EE 5.3.0

When I go to the Add-Ons section of my control panel I get this error:

Parse error: syntax error, unexpected '.', expecting ',' or ';' in /.../.../public_html/.../ee/EllisLab/Addons/rte/ext.rte.php on line 19

When I go to that line in the file (which I haven't touched and would never dream of messing with), I can see that the line in question has no issues. It's just a $docs_url with an expressionengine url as the value. There is no unexpected '.' I have used a url path to get into two of my plugins directly, bypassing the Add-Ons list page, and they seemed to work fine. It's just the Add-Ons list. Any ideas? ## 1 Answer Hrm, well that line in ext.rte.php in the 5.3.0 release is: var$docs_url       = DOC_URL.'add-ons/rte/control_panel/index.html';

So based on that error, I would assume the DOC_URL constant is not yet defined, or isn't being type interpereted as a string.

So try this:

var $docs_url = '';  If the pages loads, this smells like it could be a bug; start by using a search tool to determine where that DOC_URL constant is defined, and make sure it is getting a valid string value. You could also try hardcoding that variable to a valid value and if it works, it's another hint that DOC_URL isn't being defined. • Thanks for the response. In my ext.rte.php file that variable actually is not using the DOC_URL. It is var$docs_url = 'https://docs.expressionengine.com/v4/add-ons/rte/control_panel/index.html'; In any case, I removed it as you suggested and the page is now loading. I checked to make sure nothing was happening to the rich text editor in other places that I'm using it, and there seems to be no problems. This is odd because I do NOT touch the EE core classes, so I don't know what could have changed to cause this. Dec 10 '19 at 17:51
• I have faced this same error and checked to find this constant defined in any files. I have found the two files where this constant is defined. 1) system\ee\installer_5.3.0\controllers\wizard.php 2) system\ee\legacy\libraries\Core.php Screenshot: prntscr.com/ray4i2 Mar 3 '20 at 14:42
• I had the same problem Installed Version: 5.3.2 Build: 22-4-2020 I did edit the file found in /ee/EllisLab/Addons/rte/ext.rte.php and changed line 19 into var \$docs_url = 'add-ons/rte/control_panel/index.html'; . The error was gone, have been working since then intensively with the site without problems. Reported this as well to Robin Sowell. Jul 28 '20 at 18:20


text:
From clouds to protoplanetary disks: the astrochemical link

4-8 October 2015
Hans Harnack Haus
Europe/Berlin timezone
Home > Timetable > Session details > Contribution details

Contribution Contributed Talk

Hans Harnack Haus -
FROM CLOUDS TO DENSE CORES 1

Impulsive spot heating and thermal explosion of interstellar grains revisited

Speakers

• Dr. Alexei IVLEV

Content

The problem of impulsive heating of dust grains in cold, dense interstellar clouds is revisited theoretically, with the aim to better understand leading mechanisms of the explosive desorption of icy mantles.

It is rigorously shown that if the heating of a reactive medium occurs within a sufficiently localized spot (e.g., heating of mantles by cosmic rays), then the subsequent thermal evolution is characterized by a single dimensionless number $\lambda$. This number identifies a bifurcation between two distinct regimes: When $\lambda$ exceeds a critical value (threshold), the heat equation exhibits the explosive solution, i.e., the thermal (chemical) explosion is triggered. Otherwise, thermal diffusion causes the deposited heat to spread over the entire grain -- this regime is commonly known as the whole-grain heating.

The theory allows us to find a critical combination of the physical parameters that govern the explosion of icy mantles due to impulsive spot heating. In particular, the calculations suggest that heavy cosmic ray species (e.g., iron ions) colliding with dust are able to trigger the explosion. Based on the recently calculated local cosmic-ray spectra, the expected rate of the explosive desorption is estimated. The efficiency of the desorption, which in principle affects all solid species independent of their binding energy, is shown to be comparable with other cosmic-ray desorption mechanisms typically considered in the literature. Also, the theory allows us to estimate maximum abundances of reactive species that may be stored in the mantles, which provides important constraints on available astrochemical models.


text:
## January 26, 2007

### Breakthroughs in electronics warfare may deploy in 2 years

An advanced concept, pioneered by BAE Systems' researchers, uses light to multiply the speed and power at which HPM (High Power Microwave) pulses--powerful enough to destroy enemy electronics--can be produced without the need for explosives or huge electrical generators. This is part of revolutionary breakthrough in electronics warfare capability that will occur over the next 2-5 years and beyond. Think more controllable versions of the magnetic pulse generators in the Matrix movies.

Researchers predict leaps of 10-100 times in power output within two years. That advance could push the beam-weapon technology far beyond the 1-10-gigawatt limit of current tactical-size HPM devices. Long-standing industry estimates are that it would require a 100-gigawatt pulse for a few nanoseconds to disable a cruise missile at a useful range.

BAE Systems is not alone in the chase. Northrop Grumman and Raytheon are also building distributed array radars that can produce air-to-air and surface-to-air HPM weapons effects, contend longtime Pentagon radar specialists. In particular, the F-22, F-35, F/A-18E/F and newest F-15 radars are designed to accept modifications that would focus their beams to produce HPM energy spikes powerful enough to disable cruise, anti-aircraft, air-to-air and emitter-seeking missiles. Germany's Diehl is developing suitcase-size HPM devices that could be placed surreptitiously in a target building to damage electronics such as computers.

In addition, the U.S. military is giving classified briefings on the threat of HPM weapon technologies being developed in China and Russia. The Russians are believed to be developing radio-frequency microwave weapons for air defense, and the Chinese are developing HPM and electromagnetic pulse weapons for information warfare.

However, BAE Systems researchers claim they have made a singular leap in HPM weapons technology by combining the use of lasers and radar-like microwaves. Furthermore, the technology is scalable through the use of 4-in.-square arrays, each an integrated structure of dielectrics and electrical conductors. One hundred of them distributed over a square meter, for example, can generate up to 10 gigawatts of power, says Robert D'Amico, BAE Systems' director of advanced programs.

HPM technology can be used to detect and detonate improvised explosive devices, find suicide bombers or hidden explosives, and attacking shoulder-fired anti-aircraft missiles. The weapons can rob a foe of communications, power and mobility--while largely eliminating collateral damage to people and structures--which is a high priority for the U.S. military.

"You could put a [sensor] system on a fighter-size aircraft that could generate enough power, with a 1-ft. resolution, to see stealthy objects at 100 mi." D'Amico says. "You can defeat stealth with enough power. If stealth takes the signature [of an aircraft or missile] down a factor of 10, you have to increase the [sensor's] power by a factor of 10." Most current fighter-size radars have less than a megawatt of peak power. Detecting stealth would require tens of gigawatts, which is now impossible in fighter-size packages.

The HPM weapons could be scaled up to shipboard size--perhaps 100 sq. meters--to produce terawatt-size energy pulses. That's theoretically a large enough energy spike to stop another ship.

Researchers say the antennas, photoconductive switches and transformer blocks can be built into conformal skins for unmanned combat aircraft as well. Unmanned designs are favored initially because of the vagaries in distribution of HPM side lobes, the effects of HPM on humans, and the disturbances that energy spikes can create in fly-by-wire flight control systems.

### Entertainment and Extinction classified

Open The Future has a categorization of extinction
A futurist at the movies has listed some movie examples of the different categories

I have contributed some examples from movies, TV and some books.

Apocalypses in fiction are listed here at answers.com

LEVEL — SCALE
0 — Regional catastrophe
Movies depicting:

* 28 Days Later

1 — Human die-back
Movies depicting:

* The Day after Tomorrow
* The Postman
* Terminator

TV show
Jerimiah- Virus kills almost all adults over puberty
Various episodes of Outer Limits, twilight zone, star trek

2 — Civilizational extinction
Movies depicting:

* Deep Impact
* 12 Monkeys — due to a madman aiming for a 3A
* Planet of the Apes
* The Matrix

3A — Human extinction–engineered
Movies depicting:

* On the Beach — the apparently imminent fate of humanity after a nuclear war
* Children of Men — global sterility of unknown cause
* Independence Day — or so the aliens intend

3B — Human extinction–natural
Movies depicting:

Threat of this- South Park Goobacks of the future episode 806
http://en.wikipedia.org/wiki/Goobacks
men try to get gay in a non-procreating sex pile to eliminate future humanity
that came back to steal their jobs.

A group online actually apparently seriously calling for 3b using the no call for no sex. I refer their attempt to South Park.

4 — Biosphere extinction
Movies depicting:

Star Trek - TOS - Return to Tomorrow. The world of Sargon lost its atmosphere
Babylon 5 / Crusade : Earth gets a super-nanovirus. Will destroy all life in biosphere

5 — Planetary extinction
Movies depicting:

* Armageddon — “nothing will survive” unless the giant asteroid is deflected, though a Texas-sized asteroid might be more like a level 4

X — Planetary elimination
Movies and TV depicting:
Star Wars - A new hope
Babylon 5 - Vorlons and Shadows destroy worlds in Season 4
Star Trek- Doomsday Machine
Enterprise had an alternate timeline where the earth was destroyed.
Lensmen book - plenty of planet eliminations
Farscape - Peacekeeper Wars -planet destroyed by super wormhole

Beyond Planetary elimination
Galaxy elimination- Skylark science fiction series (EE Doc Smith)
Threat of galaxy or universe elimination - ultimate nullifier. Marvel Comics
Wellworlds books- Universe elimination

Seriously, I would create a
-1 category for more than one megadeath per year from preventable causes.
Coal pollution 1 million per year
Outdoor Air pollution which includes coal pollution 3 million per year
Car accidents 1.2 million per year
the World Health organization lists that 24% of disease are from environmental causes
The report estimates that more than 13 million deaths annually are due to preventable environmental causes. Unsanitary water, indoor air pollution.

### Entire bacteria used as controllable outboard motor

Chemicals are used to turn the bacteria on and off. They push their bead forward at speeds of around 15 microns per second. Sitti and Behkam began by sticking several S. marcescens – the kind of bacteria that cause pink stains on shower curtains – onto polystyrene beads 10 microns in diameter. These tiny "robots" were suspended in a solution containing water and glucose. To stop the bacteria's motion, the researchers add copper sulphate to the solution. The copper ions bond to the rotor of the flagella motor and prevent it from moving. To restart the motion, another chemical called ethylenediaminetetraacetic acid (EDTA) is added. The EDTA traps the copper ions attached to the rotor, allowing it to move again. The rotors can be switched off in this way an unlimited number of times. The bacteria themselves are only about one-fifth of the size of each bead and adhere to them via electrostatic, van der Waals forces and hydrophobic interactions. As the attached bacteria rotate their flagella, feeding on surrounding glucose.

### Biomimetic Technologies' project will create first soft-bodied robots

A group of researchers at Tufts University has launched a multidisciplinary initiative focused on the science and engineering of a new class of robots that are completely soft-bodied. These devices will make possible advances in such far flung arenas as medicine and space exploration.

According to Kaplan, the project will bring together biology, bioengineering and micro/nano fabrication. "Our overall goal is to develop systems and devices--soft-bodied robots--based on biological materials and on the adaptive mechanisms found in living cells, tissues and whole organisms," he explains. These devices, he notes, will have direct applications in robotics, such as manufacturing, emergency search and retrieval, and repair and maintenance of equipment in space; in medical diagnosis and treatment, including endoscopy, remote surgery, and prostheses design; and in novel electronics such as soft circuits and power supplies.

"This represents a wonderfully rich and novel collaboration that takes a comprehensive 'molecules to robots' approach to the use of soft materials," notes Linda M. Abriola, dean of the Tufts School of Engineering.

Work will focus on four primary areas: Control systems for soft-bodied robots, biomimetic and bionic materials, robot design and construction, and development and application of research-based platform technologies.

The new robots developed at Tufts will be continuously deformable and capable of collapsing and crumpling into small volumes. They will have capabilities that are not currently available in single machines including climbing textured surfaces and irregular objects, crawling along ropes and wires, or burrowing into complex confined spaces. "Soft-bodied robots could make many dangerous surgeries much safer and less painful," Trimmer adds. "They could also be used by NASA to repair space stations by reaching places that astronauts can't, perform more complicated tasks in industry that require flexibility of movement, help in hazardous environments like nuclear reactors and landmine detection, and squeeze more efficiently into tight spaces."

## January 24, 2007

When a MRL mouse’s finger is cut lower than the tip it is able to form a structure but not the full digit. Amphibians can regenerate limbs. Mammals can’t. Now two teams of bioscientists are out to correct our evolutionary shortcoming under a recent $7.6-million Darpa grant. The current goal is to produce a mammalian blastema—the cell bud that forms a new amphibian limb. In four years, Darpa wants a regrown mouse finger. Human research is the logical next step. Darpa funds will help scientists bolster preexisting research on the genetic and cellular processes of tissue regeneration. “Even if we fail,” says Muneoka, a team leader, “we’ll get better wound-healing. Mammals can already regrow limbs—to a point. Young children who lose fingertips can remake bone and tissue perfectly. The scientists believe that a mixture of cellular and extracellular components —maybe hormones, vita- min A, fibroblasts—could be applied to fresh amputations to steer them toward regeneration. “We grow a whole human in nine months,” Badylak says. “A limb should be nothing” ### Molecular memory advance This is another breakthrough that shows that molecular nanotechnology development is increasingly showing more and more impressive results on the way to major impact. A 160-kilobit memory device that is smaller than a white blood cell was made using interlocked molecules manufactured in the UCLA laboratory of J. Fraser Stoddart, director of the California NanoSystems Institute (CNSI). The research published in Nature describes the fabrication and operation of a memory device. The memory is based on a series of perpendicular, crossing nanowires, similar to a tic-tac-toe board, with 400 bottom wires and another 400 crossing top wires. Sitting at each crossing of the tic-tac-toe structure and serving as the storage element are approximately 300 bistable rotaxane molecules. These molecules may be switched between two different states, and each junction of a crossbar can be addressed individually by controlling the voltages applied to the appropriate top and bottom crossing wires, forming a bit at each nanowire crossing. The 160-kilobit molecular memory was fabricated at a density of 100,000,000,000 (10**11) bits per square centimeter — "a density predicted for commercial memory devices in approximately 2020," Stoddart said. This research is the culmination of a long-standing dream that these bistable rotaxane molecules could be used for information storage," said Stoddart, whose areas of expertise include nanoelectronics, mechanically interlocked molecules, molecular machines, molecular nanotechnology, self-assembly processes and molecular recognition, among many other fields of chemistry. "Our goal was to demonstrate that large-scale, working electronic circuits could be constructed at a density that is well-beyond — 10 to 15 years — where many of the most optimistic projections say is possible." Caltech chemists and chemical engineers, led by Heath, are the world leaders at making nanowires, according to Stoddart. "Nobody can equal them in terms of the precision with which they carry this research out," he said. The memory device’s top and bottom nanowires, each 16 nanometers wide, were fabricated using a method developed by Heath’s group. "Molecular switches will lead to other new technologies beyond molecular electronic computers." Stoddart said. "It is too soon to say precisely which ones will be the first to benefit, but they could include areas such as health care, alternative energy and homeland security. ### Why people are trying Resveratrol Wired has some anecdotes from people trying Resveratrol and other attempts to extend life. The reasoning is that Resveratrol and calorie restriction should not be harmful and might extend life. People want to live long enough and be healthy enough to take advantage of truly effective life extension methods. Perhaps methods from SENS The other aspect is that people can track their actual health markers and how they feel. Aging markers like body composition, physical performance, bone mineral density, peak aerobic capacity, Cholesterol levels, and plasma glucose and insulin levels. Here is a site that list aging biomarkers and possible treatments ### How Insect size robots will fight Wired summarizes destructive methods usable by micro robots and micro UAVs Israel is developing a robot the size of a hornet to attack terrorists. And although the prototype will not fly for three years, killer Micro Air Vehicles, or MAVs, are much closer than that. British Special Forces already use 6-inch MAV aircraft called WASPs for reconnaissance in Afghanistan. The$3,000 WASP is operated with a Gameboy-style controller and is nearly silent, so it can get very close without being detected. A new development will reportedly see the WASP fitted with a C4 explosive warhead for kamikaze attacks on snipers. One newspaper dubbed it "The Talibanator."

A MAV could put a truck out of action by destroying its tires. A MAV can do this by squirting them with few milliliters of a catalytic de-polymerization agent, causing them to disintegrate rapidly. An entire command center can be disabled by targeting the power supply. The MAV could do this by physically crawling inside like a wayward squirrel, or it might release a cloud of metal-coated fibers -- similar to the "soft bombs" the Air Force used to shut down power stations in Kosovo with a cloud of conductive whiskers.

This pdf discusses the use of poisons and stingers on MAVs

### Small fuel cells made more efficient and lower cost

Fuel cells have been made efficient for small machines like lawnmowers. Many standard fuel cell designs use electronics to control power output, but such designs require complex systems to manage humidity and fuel recovery and recycling systems to achieve acceptable efficiency.

The new process controls the hydrogen feed to match the required power output, just as one controls the feed of gasoline into an internal combustion engine. The system functions as a closed system that uses the waste water to regulate the size of the reaction chamber, the site where the gasses combine to form water, heat and electricity.

## January 23, 2007

### Life extension prospects

An article that discusses various research and possibilities for extending maximum lifespan Optimal amounts of the amino acid methionine seems to be an important part of low calorie diets. A recent Spanish study found that methionine restriction definitely decreases oxidative damage to crucial mitochondrial DNA and proteins.

Has any animal exploited the immortality of its germline to resist ageing indefinitely? The answer is yes. A few examples have been found among simpler organisms, one of the best studied being the hydra, a small freshwater animal up to 20mm long. Hydra appear to be able to regenerate endlessly with none of the recognised signs of ageing. This is possible because their bodies are permeated by germ cells whose primary purpose is to form buds that break off to yield offspring. These germ cells also create new tissue within the body, which in effect is the offspring of itself, constantly forming new cells to replace old ones. The line between reproduction and regeneration is blurred.

There is potential for humans to mimic the biologically immortal hydra, by exploiting our stem cells in the regeneration of organs damaged by age-related diseases. The ability of adult stem cells, which remain in the body throughout life, to regenerate heart muscle cells has already been demonstrated in mice. Organs regenerated this way would in effect be brand new, and "younger" than all the other tissues and organs. Such regeneration might not immediately boost life's span, but should greatly improve its quality in old age.

Possible timelines for regeneration and regenerative medicine in humans are 10-20 years

Regeneration in Chickens activated

Regneration related articles

Regenerative medicine

### Wimax, Long Term Evolution and the 4G market

Wimax will have about 20% of the next generation wireless communication market, Long Term Evolution (LTE), a follow-on to cellular's GSM standard, will command the lion's share of fourth-generation cellular systems.

MacLeod said carriers Sprint Nextel, startup Clearwire and Russia's Sistema have committed to WiMax, while Cingular and Vodafone are backing LTE. AT&T, BT and Verizon may use WiMax as an adjunct to their fiber-to-the-home deployments, and satellite broadcasters are considering WiMax as a back channel.

Qualcomm may play the role of spoiler in what some see as a two-way race between LTE and WiMax. As early as the 3GSM or CTIA conference this spring, the company will demonstrate its plans for a technology beyond wideband CDMA that could be a contender for fourth-generation cellular.

Uma Jha, a director of product management at Qualcomm, said the company will demo products that deliver 10 Mbits/second of data and have better spectral efficiency than WiMax. Qualcomm has been working with partners such as Lucent and Samsung to get its version of orthogonal frequency-division multiplexing accepted by the IEEE 802.20 group as well as the 3GPP2 group's Ultra Mobile Broadband cellular standards effort.

Carriers like Sprint are said to be attracted to WiMax primarily as a replacement for the leased lines they use to backhaul cellular traffic. But Atish Gude, senior vice president of Sprint's mobile broadband group, said one of the features that makes WiMax stand out is its ability to break old cellular business models by supporting new users and new devices, bought at retail.

Intel expects to follow up next year with devices offering a tenfold reduction in power draw. The 2008 devices will also include very low-power X86 CPUs now in design under Gadi Singer, who worked on both the Itanium server and the Xscale cellular processors at Intel.

Spectrum remains a factor limiting some WiMax uses. One carrier at last week's meeting lamented that his company could deploy WiMax in the United States today to serve rural users if the government would approve WiMax at 3.5 GHz. Many countries outside the United States allow WiMax at 3.5 GHz.

Other conference goers said the United States should open up use of WiMax at 700 MHz, where new spectrum will be available after the government reclaims analog broadcast TV airwaves in February 2009.

### Turning an axel mounted molecular wheel

Researchers at the Centre for Material Development and Structural Studies in Toulouse (CEMES-CNRS) and their colleagues at the Free University of Berlin have, for the first time, managed to control the rotation of a wheel in a molecule. This nano-mechanical experiment concerned an 0.7 nm diameter wheel attached to a 0.6 nm-long axle. This success opens the way to creating the first molecular machines. The study was published on-line on January 21, 2007, in the journal Nature Nanotechnology.

To prepare this nano-mechanical experiment, the CEMES-CNRS chemists designed and synthesised simple molecular machinery made up of an 0.6 nm-long axle-molecule, bound chemically with two triptycene wheels with a diameter of around 0.7 nm (Figure 1). The type of wheel and surface were very carefully chosen. Two notched, "tyre-less" wheels were used because of their maximum adherence to the running surface, an ultraclean copper plate. Its natural roughness presented rows of copper atoms separated by a distance of about 0.3 nm, and about one atom high.

The experiment consisted in delicately placing wheel-axle-wheel molecules on the copper surface and then using scanning tunnelling microscopy (STM) imaging at very low temperature to detect molecules lying in the correct orientation with respect to the rows of atoms on the surface. The STM tip positioned on a wheel made the latter rotate.

By advancing the STM tip, the microscope behaved like a finger to trigger the rotation.

### Fast ocean crossing boat

From the San Jose Mercury news, a boat capable of crossing ocean at a speed of 60 knots or 70 mph These are called Wave Adaptive Modular vessels.

The catamaran-like vessel has inflatable hulls, sits only about a foot deep in the water, is powered by two 355-horsepower diesel engines and has a range of up to 5,000 miles. Its relatively light weight, its range and its mobility suggest that potential uses could include search and rescue, ocean research and military applications.

### Electrovaya announces 700 Wh/liter batteries

Better batteries can make better hybrid cars, better all electric cars, and be used in a variety of space applications like powering a magbeam.

From the Energy blog, high energy density (700 Wh/liter) batteries from Electrovaya Inc. (OTC: EFLV.PK) a company in Canada The MN-Series, which is a Lithiated Manganese Oxide based system, differentiates itself from Electrovaya's Phosphate-Series solution with up to 50% higher energy density while retaining its safety characteristics. Electrovaya's proprietary Lithium Ion SuperPolymer® technology is independent of the composition of the positive electrode active material. As such, advances in positive electrode chemistry, such as the MN-Series, are expected to enable better technical performance and safety characteristics at more economical price-points. Their previous batteries were claimed to be cost competitive with other manufacturers of lithium ion or lithium ion polymer batteries, so we should expect some reduction in price.

Electrovaya’s zero emission vehicle, previous post, the MAYA-100 is powered by energy-dense, lithium-ion SuperPolymer® technology. Equipped with a 35 to 50 kWh battery pack, this long-range ZEV can travel over 200 miles between charging, at speeds up to 80 mph. In addition to the unsurpassed range, the MAYA-100 has excellent acceleration, performance and handling. Electrovaya has a major contract with NASA to power their Astronauts while on their critical space walk missions.

Electrovaya’s Li-ion superpolymer batteries presently offer an energy density of approximately 225 Wh/kg and 475 Wh/liter. The company has a research program underway to increase the cell energy density to beyond 330 Wh/kg and 650Wh/liter.

The Li-ion superpolymer batteries use a phosphate-based compound for the cathode, and a graphite/polymer anode. (Electrovaya uses a cobalt-based cathode for its mobile computing applications.) The company is targeting a cost of $270-300/kWh for the battery at moderate levels of production. The current early adopter price (2005) in North America is US$70,000 for the entire vehicle, batteries and onboard charger.

## January 22, 2007

### Geothermal not ready yet needs some research

MIT study (long PDF) on geothermal energy suggest 100GW can be generated by 2050. $300-400 million over 15 years would need to be invested in research and cost reduction for 15 years before geothermal would be cost competitive. The 100GW by 2050 figure assumes$800 million to \$1 billion over 15 years in investment in research and development (mainly prototype development and refinement).

So Geothermal is not ready now. I think the investment and research should probably be spent so that another added option is developed.

Wired discusses advances in silicon photonics In 15 or 20 years out, electrons will nearly exclusively be the stuff that computes, while photons will nearly exclusively be the stuff that communicates.

Paniccia's group at Intel will announce its fabrication of an optical modulator on a silicon chip that can translate electronic signals to light at speeds up to 20 GHz. That's nearly a threefold speedup from the group's previous modulator.

Slightly less difficult -- although still challenging -- is part three of the optics equation: making sub-millimeter-size detectors to convert the optical pulses back to electrical signals.

M.W. Geis and collaborators from MIT's Lincoln Laboratory will be announcing a breakthrough in that area this week as well: an all-silicon 10- to 20-GHz detector that, as it happens, can keep up with Intel's new modulator.

IBM has taken the lead in the middle component of the triad, microscopic silicon waveguides to pipe the information-carrying photons from the laser/modulator to the detector on the other side of the chip.

In December, Yuri Vlasov and colleagues from IBM published in the journal Nature their development of micron-size optical tracks that included storage rings. The latter devices would be used like miniature racetracks for the photons to circle around until the information they carry is needed.

These optical buffers managed to hold light for up to 60 laps around the track -- setting the buffered light pulses 10 bits behind unbuffered light.

## January 21, 2007

### Dwave roadmap has well over 1000 qubits by end of 2008

Dwave systems has a current roadmap with well over 1,000 by the end of 2008.

There are some quantum algorithms that can’t be run using the current architecture. The technical reason for this is that the devices that couple qubits i and j are of the \sigma_z^{i} \sigma_z^{j} type. There are some 16-qubit states that can’t be generated with the X + Z + ZZ Hamiltonian. Their roadmap includes the addition of an XZ coupler to their architecture, which will make their systems universal. The reason for doing this is that they plan to build processors specifically for quantum simulation, which represents a big commercial opportunity.

The current plan is to first focus on successful deployment of the X+Z+ZZ type system. Many of the hard problems in operating a X+Z+XZ type machine can be resolved in our current approach. We already have a couple good XZ coupler designs, but we probably won’t start a processor line with these until the current line’s off the ground. Our roadmap has us introducing a quantum simulation processor line in 2009.

About the scaling question: There’s no straightforward way to predict this. These systems are too complex and implementation-specific to know for sure. We will get to (and far past) the 1,000 qubit mark relatively shortly. Whether the systems will retain their current quantum behavior is unknown, but we haven’t seen anything that gives me concern about this. Part of this issue has to do with how the quantum computer is being used. The AQC approach is naturally shielded from errors in a way that the gate model isn’t, so whatever you’ve heard about error correction etc. take with a grain of salt, often these things are computational-model specific (although many people speak of them as if they were universal).

NOTE: 1000 qubits would enable 2**1000 states or about 10**300.
10**80 is the number of atoms in the observable universe
The 2009, 1000+ qubit quantum simulation processor would be a big boost for molecular nanotechnology research.

### First surgical microbot 2009

From Wired.com, An international team of scientists is developing what they say will be the world's first microrobot -- as wide as two human hairs -- that can swim through the arteries and digestive system.

The scientists are designing the 250-micron device to transmit images and deliver microscopic payloads to parts of the body outside the reach of existing catheter technology.

It will also perform minimally invasive microsurgeries, said James Friend of the Micro/Nanophysics Research Laboratory at Australia's Monash University, who leads the team. The researchers hope the device will reduce the risks normally associated with delicate surgical procedures.

While others have tried and failed to create microrobots for arterial travel, Friend believes his team will succeed because they are the first to exploit piezoelectric materials -- crystals that create an electric charge when mechanically stressed -- in their micromotor design.

Israeli scientists announced last October that they were developing a microrobot that could travel through the spinal canal.

Going into the arteries is a much more challenging proposition.

"The spinal canal is a little bit bigger, and there isn't the high flow that you have in the bloodstream, so the power that you need for the propulsion is smaller," said Shoham.

These are examples of how the vision of nanomedicine and nanobots is not unreasonable. Those who ridicule molecular nanotechnology and nanobots at this point do not know what is happening and what has happened with technology. It also shows that the examples of what molecular nanotechnology would be able to provide that were made over 20 years ago need to be updated. Engines of Creation is online as is Unbounding the Future and Eric Drexlers current website. Those illustrations were conservative based upon trying to be absolutely certain that the prediction was possible.

Reviewing the list of feasible products of molecular nanotechnology:
- medical devices able to destroy pathogens and repair tissues
See above. 250 micron robots for the bloodstream soon.

- desktop computers with a billion processors
Intel has made a prototype 80 core chip
1000 processors for under 100,000 in 2007/2008

Molecular manufacturing will still make more powerful computers but it should be something that leverages more optical communication and processing and energy and heat efficient large scale three dimensional processing.

- materials 100 times stronger than steel
carbon nanotube Superthread and the recent carbon nanotube honeycomb are here and being commercialized.
Molecular nanotechnology would bring the costs down and make even more designer materials like maybe room temperature superconductors.

- inexpensive, efficient solar energy systems
There is various advances in thin film solar
And solar cell efficiency getting to 45% and maybe higher
However, this is an area that needs for more cost reduction (which molecular nanotechnology would provide) along with the best efficiencies.

- superior military systems
See my essay on military application of molecular nanotechnology


text:
# What is the essential difference between ordinary differential equations and partial differential equations?

So many years after my undergraduate study and so many years after dealing with various concrete ODEs and PDEs, I still cannot tell the essential difference between them.

What specific belongs to PDEs but not to ODEs? What conclusion for ODEs cannot be generalized to PDEs?

At the moment, my understanding is simply that PDEs have more than one variables.

• In PDEs the geometry if often far more subtle. Aug 24 '15 at 21:16
• What I don't see in any of the answers: while for ODE the initial value problem and some boundary value problems have unique solutions (up to some constants at least), for PDE, even linear ones, there can be infinitely many completely different solutions, for example time dependent Schrodinger equation for some potentials admits a lot of mathematically valid, but unphysical solutions. Usually in applications one restricts themselves to a particular function space. Mar 10 '20 at 10:42

Both are differential equations (equations that involve derivatives). ODEs involve derivatives in only one variable, whereas PDEs involve derivatives in multiple variables. Therefore all ODEs can be viewed as PDEs.

PDEs are generally more difficult to understand the solutions to than ODEs. Basically every big theorem about ODEs does not apply to PDEs. It's more than just the basic reason that there are more variables. For an ODE, we can often view the single independent variable as a time variable, so that ODEs govern a motion or flow of an object in time. The idea of ODEs governing "motion" allows us to use many mathematical results that have analogues in physics (for example empirical behavior regarding Newton's law) and allow us to understand the solutions much more precisely.

Well, given a linear ODE, the set of solutions form a vector space with finite dimension. However, a linear PDE (like the heat equations) has a set of solution that form a vector space with infinitely many dimensions.

To see that, one may consider the ODE

$$y'=-ay(t),$$ with solution, $$y(t)=e^{-at}y_0,$$ (so, the vector space is one dimensional) Then the heat equation with periodic boundary conditions $$u_t=u_{xx},$$ has solution (use Fourier series/separation of variables) $$u(t)=\sum_{k\in\mathbb{Z}}e^{ikx}\hat{u}(k).$$ We see that the linear combination has infinitely many terms, all them linearly independent, so, the vector space has infinitely many dimensions.

Linear PDEs may not have solutions. Hans Lewy constructed such an example about sixty years ago, and it probably surprised just about everyone in the field at the time. ODEs are much nicer in that regard. http://www.jstor.org/stable/1970121?&seq=1#page_scan_tab_contents

ODE has one Independent variable, say $$x$$. Solution is $$y(x)$$.

PDE has more than one independent variables say $$(x_1,x_2,...,x_n)$$: solution is $$y(x_1,x_2,..x_n)$$. Partial derivatives are in the equation. A partial derivative differentiates with respect to one independent variable (say $$x_3$$)while holding the other independent variables constant.

Perhaps I'm missing something about your question (if so, please forgive my stupidity), but ISTM the essential difference between ODEs and PDEs == what specific[ally] belongs to PDEs but not to ODEs == ∂. Period. If the equation involves derivatives, and at least one is partial, you have a PDE. If you have a differential equation with no partial derivatives (i.e., all the equation's derivatives are total), you have an ODE. (Annoyingly for this terminology, one can also refer to total differential equations, and {TDEs} ≠ {ODEs}: rather, {TDEs} ⊆ {ODEs}.)

In addition to having more variables, PDEs also have more complex solutions than ODEs. In general, for an ODE we can often picture the solution as some sort of flow that varies with time. PDEs have more complex interpretations with the heat equation as an instance. In the heat equation the solution is such that it depends on both the position in space as well as time, and its more difficult to visualise the flow of heat as a function.

If we replace continuous derivative by its finite analog $(f(x+h)-f(x))/h$ then, in some sense, there is no difference between linear PDEs and ODEs, both with non-constant coefficients. Finite PDEs and finite ODEs generate the same $C^*$-algebra, namely universal UHF algebra $\mathbb{C}^{1\times1}\otimes\mathbb{C}^{2\times2}\otimes\mathbb{C}^{3\times3}\otimes...$ https://arxiv.org/abs/1807.09327