text:
Theorem 91.12.4 (Quillen spectral sequence). Let $A \to B$ be a surjective ring map. Consider the sheaf $\Omega = \Omega _{\mathcal{O}/A} \otimes _\mathcal {O} \underline{B}$ of $\underline{B}$-modules on $\mathcal{C}_{B/A}$, see Section 91.4. Then there is a spectral sequence with $E_1$-page

$E_1^{p, q} = H_{- p - q}(\mathcal{C}_{B/A}, \text{Sym}^ p_{\underline{B}}(\Omega )) \Rightarrow \text{Tor}^ A_{- p - q}(B, B)$

with $d_ r$ of bidegree $(r, -r + 1)$. Moreover, $H_ i(\mathcal{C}_{B/A}, \text{Sym}^ k_{\underline{B}}(\Omega )) = 0$ for $i < k$.

Proof. Let $I \subset A$ be the kernel of $A \to B$. Let $\mathcal{J} \subset \mathcal{O}$ be the kernel of $\mathcal{O} \to \underline{B}$. Then $I\mathcal{O} \subset \mathcal{J}$. Set $\mathcal{K} = \mathcal{J}/I\mathcal{O}$ and $\overline{\mathcal{O}} = \mathcal{O}/I\mathcal{O}$.

For every object $U = (P \to B)$ of $\mathcal{C}_{B/A}$ we can choose an isomorphism $P = A[E]$ such that the map $P \to B$ maps each $e \in E$ to zero. Then $J = \mathcal{J}(U) \subset P = \mathcal{O}(U)$ is equal to $J = IP + (e; e \in E)$. Moreover $\overline{\mathcal{O}}(U) = B[E]$ and $K = \mathcal{K}(U) = (e; e \in E)$ is the ideal generated by the variables in the polynomial ring $B[E]$. In particular it is clear that

$K/K^2 \xrightarrow {\text{d}} \Omega _{P/A} \otimes _ P B$

is a bijection. In other words, $\Omega = \mathcal{K}/\mathcal{K}^2$ and $\text{Sym}_ B^ k(\Omega ) = \mathcal{K}^ k/\mathcal{K}^{k + 1}$. Note that $\pi _!(\Omega ) = \Omega _{B/A} = 0$ (Lemma 91.4.5) as $A \to B$ is surjective (Algebra, Lemma 10.131.4). By Lemma 91.12.1 we conclude that

$H_ i(\mathcal{C}_{B/A}, \mathcal{K}^ k/\mathcal{K}^{k + 1}) = H_ i(\mathcal{C}_{B/A}, \text{Sym}^ k_{\underline{B}}(\Omega )) = 0$

for $i < k$. This proves the final statement of the theorem.

The approach to the theorem is to note that

$B \otimes _ A^\mathbf {L} B = L\pi _!(\mathcal{O}) \otimes _ A^\mathbf {L} B = L\pi _!(\mathcal{O} \otimes _{\underline{A}}^\mathbf {L} \underline{B}) = L\pi _!(\overline{\mathcal{O}})$

The first equality by Lemma 91.5.7, the second equality by Cohomology on Sites, Lemma 21.39.6, and the third equality as $\mathcal{O}$ is flat over $\underline{A}$. The sheaf $\overline{\mathcal{O}}$ has a filtration

$\ldots \subset \mathcal{K}^3 \subset \mathcal{K}^2 \subset \mathcal{K} \subset \overline{\mathcal{O}}$

This induces a filtration $F$ on a complex $C$ representing $L\pi _!(\overline{\mathcal{O}})$ with $F^ pC$ representing $L\pi _!(\mathcal{K}^ p)$ (construction of $C$ and $F$ omitted). Consider the spectral sequence of Homology, Section 12.24 associated to $(C, F)$. It has $E_1$-page

$E_1^{p, q} = H_{- p - q}(\mathcal{C}_{B/A}, \mathcal{K}^ p/\mathcal{K}^{p + 1}) \quad \Rightarrow \quad H_{- p - q}(\mathcal{C}_{B/A}, \overline{\mathcal{O}}) = \text{Tor}_{- p - q}^ A(B, B)$

and differentials $E_ r^{p, q} \to E_ r^{p + r, q - r + 1}$. To show convergence we will show that for every $k$ there exists a $c$ such that $H_ i(\mathcal{C}_{B/A}, \mathcal{K}^ n) = 0$ for $i < k$ and $n > c$1.

Given $k \geq 0$ set $c = k^2$. We claim that

$H_ i(\mathcal{C}_{B/A}, \mathcal{K}^{n + c}) \to H_ i(\mathcal{C}_{B/A}, \mathcal{K}^ n)$

is zero for $i < k$ and all $n \geq 0$. Note that $\mathcal{K}^ n/\mathcal{K}^{n + c}$ has a finite filtration whose successive quotients $\mathcal{K}^ m/\mathcal{K}^{m + 1}$, $n \leq m < n + c$ have $H_ i(\mathcal{C}_{B/A}, \mathcal{K}^ m/\mathcal{K}^{m + 1}) = 0$ for $i < n$ (see above). Hence the claim implies $H_ i(\mathcal{C}_{B/A}, \mathcal{K}^{n + c}) = 0$ for $i < k$ and all $n \geq k$ which is what we need to show.

Proof of the claim. Recall that for any $\mathcal{O}$-module $\mathcal{F}$ the map $\mathcal{F} \to \mathcal{F} \otimes _\mathcal {O}^\mathbf {L} B$ induces an isomorphism on applying $L\pi _!$, see Lemma 91.5.6. Consider the map

$\mathcal{K}^{n + k} \otimes _\mathcal {O}^\mathbf {L} B \longrightarrow \mathcal{K}^ n \otimes _\mathcal {O}^\mathbf {L} B$

We claim that this map induces the zero map on cohomology sheaves in degrees $0, -1, \ldots , - k + 1$. If this second claim holds, then the $k$-fold composition

$\mathcal{K}^{n + c} \otimes _\mathcal {O}^\mathbf {L} B \longrightarrow \mathcal{K}^ n \otimes _\mathcal {O}^\mathbf {L} B$

factors through $\tau _{\leq -k}\mathcal{K}^ n \otimes _\mathcal {O}^\mathbf {L} B$ hence induces zero on $H_ i(\mathcal{C}_{B/A}, -) = L_ i\pi _!( - )$ for $i < k$, see Derived Categories, Lemma 13.12.5. By the remark above this means the same thing is true for $H_ i(\mathcal{C}_{B/A}, \mathcal{K}^{n + c}) \to H_ i(\mathcal{C}_{B/A}, \mathcal{K}^ n)$ which proves the (first) claim.

Proof of the second claim. The statement is local, hence we may work over an object $U = (P \to B)$ as above. We have to show the maps

$\text{Tor}_ i^ P(B, K^{n + k}) \to \text{Tor}_ i^ P(B, K^ n)$

are zero for $i < k$. There is a spectral sequence

$\text{Tor}_ a^ P(P/IP, \text{Tor}_ b^{P/IP}(B, K^ n)) \Rightarrow \text{Tor}_{a + b}^ P(B, K^ n),$

see More on Algebra, Example 15.62.2. Thus it suffices to prove the maps

$\text{Tor}_ i^{P/IP}(B, K^{n + 1}) \to \text{Tor}_ i^{P/IP}(B, K^ n)$

are zero for all $i$. This is Lemma 91.12.3. $\square$

[1] A posteriori the “correct” vanishing $H_ i(\mathcal{C}_{B/A}, \mathcal{K}^ n) = 0$ for $i < n$ can be concluded.

Comment #7429 by Hossein Faridian on

How does one obtain the dual to Quillen's spectral sequence involving Hom and Ext? The statement is in "On the Co(homology) of Commutative Rings (Quillen)" with no proof.

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
Concavity of $\det^{1/n}$ over $HPD_n$. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T23:40:00Z http://mathoverflow.net/feeds/question/42594 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42594/concavity-of-det1-n-over-hpd-n Concavity of $\det^{1/n}$ over $HPD_n$. Denis Serre 2010-10-18T08:08:28Z 2013-04-04T07:03:33Z
One of my beloved theorems in matrix analysis is the fact that the map $H\mapsto (\det H)^{1/n}$, defined over the convex cone $HPD_n$ of Hermitian positive definite matrices, is concave. This is accurate, if we think that this map is homogeneous of degree one, thus linear over rays.

it has important applications in many branches of mathematics,

it has many elegant proofs. I know at least three complety different ones.

I am interested to learn in both aspects. Which is your prefered proof of the concavity ? Is it useful in your own speciality ? In order to avoid influencing the answers, I decide not to give any example. But those who have visited my page may know my taste.
 http://mathoverflow.net/questions/42594/concavity-of-det1-n-over-hpd-n/42635#42635 Answer by Deane Yang for Concavity of $\det^{1/n}$ over $HPD_n$. Deane Yang 2010-10-18T13:49:11Z 2010-10-18T13:49:11Z
The concavity of $(\det A)^{1/n}$ for a positive definite symmetric matrix $A$, as well as its generalization known as the Brunn-Minkowski inequality, are absolutely fundamental and critical to differential and integral geometry, as well as geometric analysis (here, I mean functional inequalities like the Sobolev and Poincare inequalities). It is used, for example, in the proof of isoperimetric inequalities and something known as the Bishop-Gromov inequality on a Riemannian manifold.

The first proof I learned is simply differentiating $(\det A(t))^{1/n}$ twice, where $A(t) = A_0 + A_1t$.
 http://mathoverflow.net/questions/42594/concavity-of-det1-n-over-hpd-n/42760#42760 Answer by Alekk for Concavity of $\det^{1/n}$ over $HPD_n$. Alekk 2010-10-19T09:33:12Z 2010-10-19T09:33:12Z
An easy reduction shows that one can suppose that one of the matrices is the identity and the other diagonal: the inequality then reduced to the convexity of $f(x)=\ln(1+e^x)$.
 http://mathoverflow.net/questions/42594/concavity-of-det1-n-over-hpd-n/126485#126485 Answer by Denis Serre for Concavity of $\det^{1/n}$ over $HPD_n$. Denis Serre 2013-04-04T07:03:33Z 2013-04-04T07:03:33Z
Here is a interesting calculus proof. Let $f:A\mapsto(\det A)^{1/n}$, defined over $SPD_n$. Differentiating twice, we find the Hessian $${\rm D}^2f_A(X,X)=\frac1{n^2}f(A)\left(({\rm Tr} M)^2-n{\rm Tr}(M^2)\right),$$ where $M=A^{-1}X$. This matrix, being the product of two symmetric matrices with one of them positive definite, is diagonalisable with real eigenvalues $m_1,\ldots,m_n$. The parenthesis above is now $$\left(\sum_jm_j\right)^2-n\sum_jm_j^2,$$ a non-positive quantity, according to Cauchy-Schwarz. We infer that ${\rm D}^2f_A\le0$ and that $f$ is concave.

format: plain


text:
## A brief history about development of String Theories

---------------------------------------------------------------------
References:

1) Green M., Schwarz J., Witten E., Superstring Theory Vol. 1,2, Cambridge Univ. Press, 1987
2) S.Klimenko, V.Talanov, I.Nikitin Singularities on the world sheets of open relativistic strings'', Preprint IHEP 95-7, (Institute for High Energy Physics, Protvino, Russia, 1995).
3) Introduction to Superstring Theory {http://www.arxiv.org/abs/hep-ex/0008017)
4) "String theory in a nutshell" written by (JM Figueroa-O'Farrill)
{http://www.strings.ph.qmw.ac.uk/WhatIs/Nutshell.html}

---------------------------------------------------------------------
 PhysOrg.com physics news on PhysOrg.com >> Cheap, color, holographic video: Better holographic video displays>> First entanglement between light and optical atomic coherence>> EUROnu project recommends building Neutrino Factory
 Blog Entries: 6 Recognitions: Gold Member Good text, excet by the fuzzy concept of "newtonian paradigm". One should clarify why it is a model, why it is from Newton, and how it does realte to strings after all. Also, I'd like to include the recent (a couple years old by now) ideas of reusing the string in its original context, in QCD, and some more mentions to submilimeter dimensions etc.
 You might also want to find some place in your text to note that string theory makes no predictions and there is not the slightest shred of experimental evidence for it after twenty years of work on the idea. Or, alternately, you could explain how an increasingly large number of string theorists think that if string theory makes sense, it is completely vacuous, since the "landscape" of its 10^1000 or more solutions can give you any predictions about physics you want.

Recognitions:
Gold Member
Science Advisor
Staff Emeritus

## A brief history about development of String Theories

 Originally posted by arivero *SNIP ... and some more mentions to submilimeter dimensions etc.
AFAIK there've been quite a few experiments done to look for deviations from inverse square law gravity (for example), down to ~1 micron. Have there been any results other than NULL? What other objectives have sub-mm experiments had?
 Blog Entries: 6 Recognitions: Gold Member Perhaps a goal of submilimeter stuff, but also of Randrall Sundrum etc, was to bring back gradually into reality to the string theoreticians far far away the standard model. At the end the string theory could recover its original rule as a phase of SU(3)...
 Recognitions: Gold Member Science Advisor Staff Emeritus We do not condone plagiarism here on physicsforums. If you copy someone else's work, you must provide at least a link to the original, if not a full citation including the author's name. For reference, the original text is available here: http://www.strings.ph.qmw.ac.uk/WhatIs/Nutshell.html and was written by JM Figueroa-O'Farrill. - Warren

 Similar discussions for: A brief history about development of String Theories Thread Forum Replies General Physics 8 Beyond the Standard Model 3 Beyond the Standard Model 9 Quantum Physics 1 Beyond the Standard Model 6


text:
## VanillaAngelic one year ago The length of a rectangle is 12 inches, and its diagonal measures 13 inches. Find the area of that rectangle. Please explain step by step.

1. anonymous

$\sqrt{13^2-12^2}=5$ 12*5 = 60 sq in

2. VanillaAngelic

Thank you.


text:
The difference between the expanding and rolling window in Pandas

In Pandas, there are two types of window functions. In this article, I am going to demonstrate the difference between them, explain how to choose which function to use, and show you how to deal with datetime in window functions.

First, let’s create a dataset I am going to use as an example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import pandas as pd
data = pd.DataFrame([
['a', 1],
['a', 2],
['a', 3],
['b', 5],
['b', 6],
['b', 7],
['b', 8],
['c', 10],
['c', 11],
['c', 12],
['c', 13]
], columns = ['category', 'value'])

Using expanding windows to calculate the cumulative sum

If I use the expanding window with initial size 1, I will create a window that in the first step contains only the first row. In the second step, it contains both the first and the second row. In every step, one additional row is added to the window, and the aggregating function is being recalculated.

1
data.value.expanding(1).sum()

As a result, I get that output:

1
2
3
4
5
6
7
8
9
10
11
0      1.0
1      3.0
2      6.0
3     11.0
4     17.0
5     24.0
6     32.0
7     42.0
8     53.0
9     65.0
10    78.0

Rolling window over n rows

Rolling windows are totally different. In this case, we specify the size of the window which is moving. What happens when I set the rolling window size to 2?

In the first step, it is going to contain the first row and one undefined row, so I am going to get NaN as a result.

In the second step, the window moves and now contains the first and the second row. Now it is possible to calculate the aggregate function. In the case of this example, the sum of both rows.

In the third step, the window moves again and no longer contains the first row. Instead of that now it calculates the sum of the second and the third row.

1
data.value.rolling(2).sum()

The output:

1
2
3
4
5
6
7
8
9
10
11
0      NaN
1      3.0
2      5.0
3      8.0
4     11.0
5     13.0
6     15.0
7     18.0
8     21.0
9     23.0
10    25.0

Avoiding NaN in the results from rolling windows

What to do when I want to get aggregated results in the rows which contain undefined values? I can specify the minimum number of defined values in a window, by using the min_periods parameter:

1
data.value.rolling(2, min_periods = 1).sum()

The result:

1
2
3
4
5
6
7
8
9
10
11
0      1.0
1      3.0
2      5.0
3      8.0
4     11.0
5     13.0
6     15.0
7     18.0
8     21.0
9     23.0
10    25.0

Rolling windows using datetime

Instead of defining the number of rows, it is also possible to use a datetime column as the index and define a window as a time period.

Unfortunately, it is unintuitive and does not work when we use weeks or months as the time period.

Let’s see what is the problem. First, I have to create a new data frame.

1
2
3
4
5
6
7
8
9
10
11
12
13
data = pd.DataFrame([
[pd.to_datetime('2019-05-01 00:10:00Z'), 1],
[pd.to_datetime('2019-05-01 01:00:00Z'), 1],
[pd.to_datetime('2019-05-01 02:04:12Z'), 1],
[pd.to_datetime('2019-05-02 10:03:00Z'), 1],
[pd.to_datetime('2019-05-02 11:21:00Z'), 1],
[pd.to_datetime('2019-05-02 17:00:00Z'), 1],
[pd.to_datetime('2019-05-03 03:12:34Z'), 1],
[pd.to_datetime('2019-05-03 08:23:12Z'), 1],
[pd.to_datetime('2019-05-04 10:24:10Z'), 1],
[pd.to_datetime('2019-05-07 19:03:57Z'), 1],
[pd.to_datetime('2019-05-11 23:59:12Z'), 1]
], columns = ['time', 'value'])

Now, in the window function, I must specify the column which should be used as the index (or have the data frame indexed by the time values) and use the time range to define the size of the rolling window. In this case, I am going to sum the values grouped by days.

1
data.rolling('D', on = 'time', min_periods = 1).sum()

The result:

1
2
3
4
5
6
7
8
9
10
11
12
time  value
0  2019-05-01 00:10:00+00:00    1.0
1  2019-05-01 01:00:00+00:00    2.0
2  2019-05-01 02:04:12+00:00    3.0
3  2019-05-02 10:03:00+00:00    1.0
4  2019-05-02 11:21:00+00:00    2.0
5  2019-05-02 17:00:00+00:00    3.0
6  2019-05-03 03:12:34+00:00    4.0
7  2019-05-03 08:23:12+00:00    5.0
8  2019-05-04 10:24:10+00:00    1.0
9  2019-05-07 19:03:57+00:00    1.0
10 2019-05-11 23:59:12+00:00    1.0

Do you see the issue? The moving window ends when there is at least 24 hours difference between the values, so I can’t use it to group my example rows by the calendar date.

If I used weeks (or months), it would be even worse, because I would get this error:

1
<Week: weekday=6> is a non-fixed frequency

The correct way

To get the expected result, (dates grouped by calendar dates + cumulative sum of values within the day) I have to drop the time part of the datetime value, group the rows by the date and calculate the cumulative sum.

1
2
3
4
5
6
7
8
9
# drop the time from datetime
data['without_time'] = data['time'].dt.date

#calculate the cumulative sum by day
sums = data.groupby('without_time').cumsum()
sums.columns = ['cumulative_sum']

#put the result as a column in the original dataframe
pd.concat([data, sums], axis = 1).drop(columns = ['without_time'])

The result:

1
2
3
4
5
6
7
8
9
10
11
12
time  value  cumulative_sum
0  2019-05-01 00:10:00+00:00      1               1
1  2019-05-01 01:00:00+00:00      1               2
2  2019-05-01 02:04:12+00:00      1               3
3  2019-05-02 10:03:00+00:00      1               1
4  2019-05-02 11:21:00+00:00      1               2
5  2019-05-02 17:00:00+00:00      1               3
6  2019-05-03 03:12:34+00:00      1               1
7  2019-05-03 08:23:12+00:00      1               2
8  2019-05-04 10:24:10+00:00      1               1
9  2019-05-07 19:03:57+00:00      1               1
10 2019-05-11 23:59:12+00:00      1               1

Remember to share on social media!


text:
# Question #56b8e

${v}_{r m s} = \sqrt{\frac{3 R T}{M}}$
where $R = 8.31447 J m o {l}^{-} 1 {K}^{-} 1$
$M =$ the molar mass of the substance, expressed in kilograms
and $T$ is temperature of the sample in Kelvin.
${v}_{r m s} = \sqrt{\frac{3 \times 8.31447 \times 265}{32 \times {10}^{-} 3}}$
$= 454.5 m {s}^{-} 1$, rounded to one decimal place.


text:
# I Tensor Products of Modules - Bland - Remark, Page 65

1. Jun 4, 2016

### Math Amateur

I am reading Paul E. Bland's book "Rings and Their Modules ...

Currently I am focused on Section 2.3 Tensor Products of Modules ... ...

I need some help in order to fully understand the Remark that Bland makes on Pages 65- 66

Bland's remark reads as follows:

Question 1

In the above text by Bland we read the following:

"... ... but when $g$ is specified in this manner it is difficult to show that it is well defined ... ... "

What does Bland mean by showing $g$ is well defined and why would this be difficult ... ...

Question 2

In the above text by Bland we read the following:

"... ... Since the map $h = \rho' ( f \times id_N )$ is an R-balanced map ... ... "

Why is $]h = \rho' ( f \times id_N )$ an R-balanced map ... can someone please demonstrate that this is the case?

Hope someone can help ... ...

Peter

=============================================================================

The following text including some relevant definitions may be useful to readers not familiar with Bland's textbook... note in particular the R-module in Bland's text means right R-module ...

#### Attached Files:

File size:
39.5 KB
Views:
117
File size:
121.6 KB
Views:
119
• ###### Bland - R-Balanced Maps and Tensor Products.png
File size:
99.4 KB
Views:
114
Last edited: Jun 4, 2016
2. Jun 4, 2016

### andrewkirk

Good morning MA. I wonder if you are affected by the wild weather this morning from the East Coast Low in the Tasman Sea.

In the example given, the purported definition of $g$ is that $g(x\otimes y)=f(x)\otimes y$. If we think about what this means, it is saying that

$$g\Big(\chi_{(x,y)}+K\Big)=\chi_{(f(x),y)}+K'$$

where $K$ and $K'$ are the submodules of $Z$ and $Z'$ respectively that have the required 'zero' properties inherited from the modules $M,M',N$; and $Z$ and $Z'$ are the free R-modules generated by ${\{\chi_{(u,v)}\ :\ u\in M\wedge v\in N\}}$ and ${\{\chi_{(u,v)}\ :\ u\in M'\wedge v\in N\}}$ respectively.

For this to be well-defined, we require that, for any $a,c\in M$ and $b,d\in N$ such that $(a,b)$ and $(c,d)$ are in the same coset of $K$, it will be the case that $(f(a),b))$ and $(f(c),d)$ are in the same coset of $K'$. Otherwise, $g$ will not be a function because $g\Big(\chi_{(a,b)}+K\Big)\neq g\Big(\chi_{(c,d)}+K\Big)$ even though $\chi_{(a,b)}+K=\chi_{(c,d)}+K$. Hence we have two different output values for a single input.

The argument involving the diagram appears to be a proof that $g$, thus defined, is indeed well-defined.

3. Jun 4, 2016

### Math Amateur

Hi Andrew ... thanks for helping ///

I am currently in regional Victoria ... back in Tasmania soon ... weather wet and cold here but not wild like around Sydney and the NSW coastline ...

Regarding you post ... yes, understand ... so what you are saying is ... ... that when Bland talks about $g$ being "well defined" he means that if we choose a different element ... say, $\sum_{ i = 1}^m n'_i ( x'_i \otimes y'_i )$ in the same coset as $\sum_{ i = 1}^m n_i ( x_i \otimes y_i )$ ... ... then $g$ still maps onto $\sum_{ i = 1}^m n_i ( f(x_i) \otimes y_i )$ ... ... is that correct ...?

4. Jun 5, 2016

### andrewkirk

Yes, that's right.

5. Jun 5, 2016

### Math Amateur

Thanks Andrew ...

Peter

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted


text:
# Importing the New Zealand Income Survey SURF

## At a glance:

I tidy up the publicly available simulated unit record file (SURF) of the New Zealand Income Survey 2011, import into a database, and explore income distributions, visualising the lower distribution of weekly incomes New Zealanders of Maori and Pacific Islander ethnicity. Along the way I create a function to identify modes in a multi-modal distribution.

15 Aug 2015

## The quest for income microdata

For a separate project, I've been looking for source data on income and wealth inequality. Not aggregate data like Gini coefficients or the percentage of income earned by the bottom 20% or top 1%, but the sources used to calculate those things. Because it's sensitve personal financial data either from surveys or tax data, it's not easy to get hold of, particularly if you want to do it in the comfort of your own home and don't have time / motivation to fill in application forms. So far, what I've got is a simulated unit record file (SURF) from the New Zealand Income Survey, published by Statistics New Zealand for educational and instructional purposes. It's a simplified, simulated version of the original survey and it lets me make graphics like this one:

This plot shows the density of income from all sources for four of the most prominent ethnicity types in New Zealand. New Zealand official statistics allow people to identify with more than one ethnicity, which means there is some double counting (more on that below). Three things leap out at me from this chart:

1. The density curves of the different ethnic groups are very similar visually
2. People of Maori and Pacific Peoples ethnicity have proportionately more $300-$400 per week earners than Europeans and Asians, leading to an overall noticeable lean to the lower numbers
3. Weekly income is bimodal, bunching up at $345 per week and$820 per week. Actually, this image is misleading in that respect; in reality it is trimodal, with a huge bunch of people with zero income (and some negative), who aren't shown on this plot because of the logarithmic scale. So you could say that, for New Zealanders getting any income at all, there is a bimodal distribution.

Where's that bimodal distribution coming from? The obvious candidate is part time workers, and this is seen when we plot income versus hours worked in the next image:

(That interesting diagonal line below which there are very few points is the minimum wage per hour)

Statistics New Zealand warn that while this simulated data is an accurate representation of the actual New Zealand population, it shouldn't be used for precise statistics, so for now I won't draw particularly strong conclusions on anything. A simulated unit record file is a great way of solving confidentiality purposes, but in the end it has been created by a statistical model. There's a risk that interesting inferences might be just picking up something implicit in the model that wasn't taken into account when it was first put together. That's not likely to be the case for the basic distribution of the income values, but we'll note the exploratory finding for now and move on.

A box plot is better for examining the full range of reported ethnicities but not so good for picking up the bi-modal subtlety. It should also be noted that both these graphs delete people who made losses (negative income) in a given week - the data show income from all sources:

Here's how I drew the graphs, and estimated the two modes. I think I'll want to re-use this data quite often, so it's worth while putting in a database that's accessible from different projects without having to move a bunch of data files around in Windows Explorer. The way Statistics New Zealand have released the file, with codings rather than values for dimensions like ethnicity and region, also makes a database a good way to make the data analysis ready.

After importing the data, the first significant job is to deal with that pesky ethnicity variable. In the released version of the data respondents with two ethnicities have both code numbers joined together eg 12 means both European (1) and Maori (2). To get around this I split the data into two fact tables, one with a single row per respondent with most of the data; and a second just for ethnicity with either one or two rows for each respondent. Here's how I do that with a combination of {dplyr} and {tidyr}:

Second step is to re-create the dimension tables that turn the codes (eg 1 and 2) into meaningful values (European and Maori). Statistics New Zealand provide these, but unfortunately in an Excel workbook that's easier for humans than computers to link up to the data. There's not too many of so it's easy enough to code them by hand, which the next set of code does:

The final step in the data cleaning is to save all of our tables to a database, create some indexes so they work nice and fast, and join them up in an analysis-ready view. In the below I use an ODBC (open database connectivity) connection to a MySQL server called "PlayPen". R plays nicely with databases; set it up and forget about it.

## Average weekly income in NZ 2011 by various slices and dices

Whew, that's out of the way. Next post that I use this data I can go straight to the database. We're now in a position to check our data matches the summary totals provided by Statistics New Zealand. Statistics New Zealand say this SURF can be treated as a simple random sample, which means each point can get an identical individual weight, which we can estimate from the summary tables in their data dictionary. Each person in the sample represents 117.4 in the population (in the below I have population figures in thousands, to match the Statistics New Zealand summaries.

Statistics New Zealand doesn't provide region and occupation summary statistics, and the qualification summaries they provide use a more detailed classification than is in the actual SURF. But for the other categories - sex, age group, and the trick ethnicity - my results match theirs, so I know I haven't munched the data.

sex Mean Sample Population
female 611 15217 1787.10
male 779 14254 1674.00
agegrp Mean Sample Population
15-19 198 2632 309.10
20-24 567 2739 321.70
25-29 715 2564 301.10
30-34 796 2349 275.90
35-39 899 2442 286.80
40-44 883 2625 308.30
45-49 871 2745 322.40
50-54 911 2522 296.20
55-59 844 2140 251.30
60-64 816 1994 234.20
65+ 421 4719 554.20
qualification Mean Sample Population
School 564 7064 829.60
None 565 6891 809.30
Other 725 1858 218.20
Bachelor or Higher 955 5223 613.40
occupation Mean Sample Population
No occupation 257 10617 1246.90
Labourers 705 2154 253.00
Residual Categories 726 24 2.80
Community and Personal Service Workers 745 1734 203.60
Sales Workers 800 1688 198.20
Clerical and Adminsitrative Workers 811 2126 249.70
Technicians and Trades Workers 886 2377 279.20
Machinery Operators and Drivers 917 1049 123.20
Professionals 1105 4540 533.20
Managers 1164 3162 371.30
region Mean Sample Population
Bay of Plenty 620 1701 199.80
Taranaki 634 728 85.50
Waikato 648 2619 307.60
Southland 648 637 74.80
Manawatu-Wanganui 656 1564 183.70
Northland 667 1095 128.60
Nelson/Tasman/Marlborough/West Coast 680 1253 147.20
Otago 686 1556 182.70
Gisborne / Hawke's Bay 693 1418 166.50
Canterbury 701 4373 513.60
Auckland 720 9063 1064.40
Wellington 729 3464 406.80
ethnicity Mean Sample Population
Residual Categories 555 85 10.00
Maori 590 3652 428.90
Pacific Peoples 606 1566 183.90
Middle Eastern/Latin American/African 658 343 40.30
Asian 678 3110 365.20
European 706 22011 2585.00
Other Ethnicity 756 611 71.80

## Graphics showing density of income

Finally, here's the code that drew the charts we started with, showing the distribution of the weekly income New Zealanders of different ethnicity.

Edited 18 August 2015 to add the scatter plot of the joint density of hours and income.


text:
Complexity theoretical results on nondeterministic graph-driven read-once branching programs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 1, pp. 51-66.

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model $M$ is the test whether a given BP is really a BP of model $M$. Here it is proved that the consistency test is co-NP-complete for nondeterministic (parity) graph-driven BP1s. Moreover, a lower bound technique for nondeterministic graph-driven BP1s is presented. The method generalizes a technique for the well-structured model and is applied in order to answer in the affirmative the open question whether the model of nondeterministic graph-driven BP1s is a proper restriction of nondeterministic BP1s (with respect to polynomial size).

DOI : https://doi.org/10.1051/ita:2003010
Classification : 68Q05,  68Q15,  94C10
Mots clés : computational complexity, read-once branching programs, nondeterminism, lower bounds
@article{ITA_2003__37_1_51_0,
author = {Bollig, Beate},
title = {Complexity theoretical results on nondeterministic graph-driven read-once branching programs},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {51--66},
publisher = {EDP-Sciences},
volume = {37},
number = {1},
year = {2003},
doi = {10.1051/ita:2003010},
zbl = {1084.68049},
mrnumber = {1991751},
language = {en},
url = {http://www.numdam.org/item/ITA_2003__37_1_51_0/}
}
Bollig, Beate. Complexity theoretical results on nondeterministic graph-driven read-once branching programs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 1, pp. 51-66. doi : 10.1051/ita:2003010. http://www.numdam.org/item/ITA_2003__37_1_51_0/

[1] M. Ajtai, A non-linear time lower bound for boolean branching programs, in Proc. of 40th FOCS (1999) 60-70. | MR 1916185

[2] P. Beame, M. Saks, X. Sun and E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation, in Proc. of 41st FOCS (2000) 169-179. | MR 1931815

[3] P. Beame and E. Vee, Time-space trade-offs, multiparty communication complexity, and nearest neighbor problems, in Proc. of 34th STOC (2002) 688-697. | MR 2121196

[4] B. Bollig, Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication. RAIRO: Theoret. Informatics Appl. 35 (2001) 149-162. | Numdam | MR 1862460 | Zbl 0992.68057

[5] B. Bollig, St. Waack and P. Woelfel, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, in Proc. of 2nd IFIP International Conference on Theoretical Computer Science (2002) 83-94.

[6] B. Bollig and P. Woelfel, A lower bound technique for nondeterministic graph-driven read-once branching programs and its applications, in Proc. of MFCS 2002. Springer, Lecture Notes in Comput. Sci. 2420 (2002) 131-142. | MR 2064452 | Zbl 1014.68504

[7] A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-$k$-times branching programs. Comput. Complexity 3 (1993) 1-18. | MR 1220075 | Zbl 0777.68043

[8] H. Brosenne, M. Homeister and St. Waack, Graph-driven free parity BDDs: Algorithms and lower bounds, in Proc. of MFCS. Springer, Lecture Notes in Comput. Sci. 2136 (2001) 212-223. | MR 1907013 | Zbl 0999.68068

[9] R.E. Bryant, Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. | Zbl 0593.94022

[10] J. Gergov and C. Meinel, Frontiers of feasible and probabilistic feasible boolean manipulation with branching programs, in Proc. of STACS. Springer, Lecture Notes in Comput. Sci. 665 (1993) 576-585. | MR 1244146 | Zbl 0798.68078

[11] J. Gergov and C. Meinel, Efficient boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. Comput. 43 (1994) 1197-1209. | Zbl 1063.68573

[12] J. Hromkovič, Communication Complexity and Parallel Computing. Springer (1997). | MR 1442518 | Zbl 0873.68098

[13] M. Krause, BDD-based cryptanalysis of keystream generators, in Proc. of EUROCRYT (2002) 222-237. | MR 1975536 | Zbl 1055.94018

[14] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). | MR 1426129 | Zbl 0869.68048

[15] J. Jain, J. Bitner, D.S. Fussell and J.A. Abraham, Functional partitioning for verification and related problems. Brown/MIT VLSI Conference (1992) 210-226.

[16] E.I. Nechiporuk, On a boolean function. Soviet Math. Dokl. 7 (1966) 999-1000. | Zbl 0161.00901

[17] A.A. Razborov, Lower bounds for deterministic and nondeterministic branching programs, in Proc. of FCT. Springer, Lecture Notes in Comput. Sci. 529 (1991) 47-60. | MR 1136069

[18] P. Savický and D. Sieling, A hierarchy result for read-once branching programs with restricted parity nondeterminism, in Proc. of 25th MFCS. Springer, Lecture Notes in Comput. Sci. 1893 (2000) 650-659. | MR 1844789 | Zbl 0996.68513

[19] P. Savický and S. Žák, A read-once lower bound and a $\left(1,+k\right)$-hierarchy for branching programs. Theoret. Comput. Sci. 238 (2000) 347-362. | MR 1760487 | Zbl 0947.68056

[20] D. Sieling and I. Wegener, I. (1995). Graph driven BDDs - A new data structure for boolean functions. Theoret. Comput. Sci. 141 (1995) 283-310. | Zbl 0873.68036

[21] D. Sieling and I. Wegener, A comparison of free BDDs and transformed BDDs. Formal Meth. System Design 19 (2001) 223-236. | Zbl 1053.68071

[22] J. Thathachar, On separating the read-$k$-times branching program hierarchy, in Proc. of 30th Ann. ACM Symposium on Theory of Computing (STOC) (1998) 653-662. | MR 1715611 | Zbl 1006.68054

[23] I. Wegener, The Complexity of boolean Functions. Wiley-Teubner (1987). | MR 905473 | Zbl 0623.94018

[24] I. Wegener, Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000). | Zbl 0956.68068

[25] P. Woelfel, A lower bound technique for restricted branching programs and applications, in Proc. of 19th STACS. Springer, Lecture Notes in Comput. Sci. 2285 (2002) 431-442. | MR 2050857 | Zbl 1054.68554


text:
# Understanding memory mapping conceptually

I've already read several blogs and questions on stack exchange, but I'm unable to grasp what the real drawbacks of memory mapped files are. I see the following are frequently listed:

1. You can't memory map large files (>4GB) with a 32-bit address space.

QUESTION #1: Why? Isn't that the whole point of virtual memory? If a file is greater than 4GB, it may cause trashing by swapping out some memory mapped pages, but why is there a limitation?

1. If the application is trying to read from a part of the file that is not loaded in the page cache, it (the application) will incur a penalty in the form of a page-fault, which in turn means increased I/O latency for the operation.

QUESTION #2: Isn't this the case for a standard file I/O operation as well? If an application tries to read from a part of a file that is not yet cached, it will result in a syscall that will cause the kernel to load the relevant page/block from the device. And on top of that, the page needs to be copied back to the user-space buffer.

Is the concern here that page-faults are somehow more expensive than syscalls in general - my interpretation of what Linus Torvalds says here? Is it because page-faults are blocking => the thread is not scheduled off the CPU => we are wasting precious time? Or is there something I'm missing here?

1. Overhead of kernel mappings and data structures - according to Linus Torvalds. I won't even attempt to question this premise, because I don't know much about the internals of Linux kernel. :)

2. No support for async I/O for memory mapped files.

QUESTION #3: Is there an architectural limitation with supporting async I/O for memory mapped files, or is it just that it no one got around to doing it?

1. One drawback that I thought of was that if too many files are memory mapped, this can cause lower available system resources (memory) => can cause pages to be evicted => potentially more page faults. So some prudence is required in deciding what files to memory map and their access patterns.

• Q1: because with 32-bits you can address only $2^{32}$ blocks. And each block is a single byte in case of memory mapping. Sep 5 '19 at 8:40
Re #1: If your address space is 32 bits, you can address only 4GiB by pointers into memory. You can process larger files by e.g. reading the sequentially, or lseek(2) into it (note that usually off_t is a 64-bit type today).


text:
# American Institute of Mathematical Sciences

March  2016, 15(2): 413-428. doi: 10.3934/cpaa.2016.15.413

## Multi-bump positive solutions of a fractional nonlinear Schrödinger equation in $\mathbb{R}^N$

 1 School of Mathematics and Statistics, Hubei Normal University, Huangshi, 435002, China, China

Received  March 2015 Revised  December 2015 Published  January 2016

In this paper, we study a fractional nonlinear Schrödinger equation. Applying the finite reduction method, we prove that the equation has multi-bump positive solutions under some suitable conditions which are given in section 1.
Citation: Weiming Liu, Lu Gan. Multi-bump positive solutions of a fractional nonlinear Schrödinger equation in $\mathbb{R}^N$. Communications on Pure & Applied Analysis, 2016, 15 (2) : 413-428. doi: 10.3934/cpaa.2016.15.413
##### References:
 [1] X. Cabré and J. Tan, Positive solutions of nonlinear problems involving the square root of the Laplacian, Adv. Math., 224 (2010), 2052-2093. Google Scholar [2] W. Choi, S. Kim and K. A. Lee, Asymptotic behavior of solutions for nonlinear elliptic problems with the fractional Laplacian, J. Funct. Anal., 266 (2014), 6531-6598. Google Scholar [3] X. Chang and Z. Q. Wang, Nodal and multiple solutions of nonlinear problems involving the fractional Laplacian, J. Differential Equations, 256 (2014), 2956-2992. Google Scholar [4] G. Chen and Y. Zheng, Concentration phenomenon for fractional nonlinear Schrödinger equations, Commun. Pure Appl. Anal., 13 (2014), 2359-2376. Google Scholar [5] J. Dávila, M. Del Pino and J. Wei, Concentration standing waves for the fractional nonlinear Schrödinger equation, J. Differential Equations, 256 (2014), 858-892. Google Scholar [6] S. Dipierro, G. Palatucci and E. Valdinoci, Existence and symmetry results for a Schrödinger type problem involving the fractional Laplacian, Matematiche, 68 (2013), 201-216. Google Scholar [7] B. Feng, Ground states for the fractional nonlinear Schrödinger equation, J. Differential Equations, 127 (2013), 1-11. Google Scholar [8] Rupert Frank, Enno Lenzmann and Luis Silvestre, Uniqueness and nondegeneracy of ground states for $(-\Delta)^sQ + Q - Q^{\alpha+1} = 0$ in $R$, Acta Math., 210 (2013), 261-318. Google Scholar [9] Rupert Frank and Enno Lenzmann, Uniqueness of radial solutions for the fractional Laplacian,, \emph{Commun. Pure Appl. Math.}, ().   Google Scholar [10] P. Felmer, A. Quass and J. Tan, Positive solutions of nonlinear Schrödinger equation with the fractional Laplacian, Proc. Roy. Soc. Edinburgh Sect. A, 142 (2012), 1237-1262. Google Scholar [11] N. Laskin, Fractional quantum mechanics and L'evy path integrals, Phys. Lett. A, 268 (2000), 29-305. Google Scholar [12] N. Laskin, Fractional Schrödinger equation, Phys. Rev. E, 66 (2002), 31-35. Google Scholar [13] L. Lin, Z. Liu and S. Chen, Multi-bump solutions for a semilinear Schrödinger equation, Phys. Rev. E, 58 (2009), 1659-1689. Google Scholar [14] W. Long, S. Peng and J. Yang, Infinitely many positive and sign-changing solutions for nonlinear fractional scalar field equations, Discret. Contin. Dynam. Syst., 36 (2016), 917-939. Google Scholar [15] E. S. Noussair and S. Yan, On positive multi-peak solutions of a nonlinear elliptic problem, J. Lond. Math. Soc., 62 (2000), 213-227. Google Scholar [16] E. Di Nezza, G. Palatucci and E. Valdinoci, Hitchhiker's guide to the fractional Sobolev spaces, Bull. Sci. Math., 136 (2012), 521-573. Google Scholar [17] G. Palatucci and A. Pisante, Improved sobolev embeddings, profile decomposition and concentration-compactness for fractional sobolev spaces, Calc. Var. Partial Differential Equations, 50 (2014), 799-829. Google Scholar [18] S. Secchi, Ground state solutions for nonlinear fractional Schrödinger equations in $R^N$, J. Math. Phys., 54 (2013), 031501, 17 pp. Google Scholar [19] X. Shang and J. Zhang, Concentrating solutions of nonlinear fractional Schrödinger equation with potentials, J. Differ. Equ., 258 (2015), 1106-1128. Google Scholar [20] J. Tan, The Brezis-Nirenberg type problem involving the square root of the Laplacian, Calc. Var. Partial Differential Equations, 42 (2011), 21-41. Google Scholar [21] L. Wang and C. Zhao, Infinitely many solutions to a fractional nonlinear Schrödinger equation,, arXiv:1403.0042., ().   Google Scholar

show all references

##### References:
 [1] X. Cabré and J. Tan, Positive solutions of nonlinear problems involving the square root of the Laplacian, Adv. Math., 224 (2010), 2052-2093. Google Scholar [2] W. Choi, S. Kim and K. A. Lee, Asymptotic behavior of solutions for nonlinear elliptic problems with the fractional Laplacian, J. Funct. Anal., 266 (2014), 6531-6598. Google Scholar [3] X. Chang and Z. Q. Wang, Nodal and multiple solutions of nonlinear problems involving the fractional Laplacian, J. Differential Equations, 256 (2014), 2956-2992. Google Scholar [4] G. Chen and Y. Zheng, Concentration phenomenon for fractional nonlinear Schrödinger equations, Commun. Pure Appl. Anal., 13 (2014), 2359-2376. Google Scholar [5] J. Dávila, M. Del Pino and J. Wei, Concentration standing waves for the fractional nonlinear Schrödinger equation, J. Differential Equations, 256 (2014), 858-892. Google Scholar [6] S. Dipierro, G. Palatucci and E. Valdinoci, Existence and symmetry results for a Schrödinger type problem involving the fractional Laplacian, Matematiche, 68 (2013), 201-216. Google Scholar [7] B. Feng, Ground states for the fractional nonlinear Schrödinger equation, J. Differential Equations, 127 (2013), 1-11. Google Scholar [8] Rupert Frank, Enno Lenzmann and Luis Silvestre, Uniqueness and nondegeneracy of ground states for $(-\Delta)^sQ + Q - Q^{\alpha+1} = 0$ in $R$, Acta Math., 210 (2013), 261-318. Google Scholar [9] Rupert Frank and Enno Lenzmann, Uniqueness of radial solutions for the fractional Laplacian,, \emph{Commun. Pure Appl. Math.}, ().   Google Scholar [10] P. Felmer, A. Quass and J. Tan, Positive solutions of nonlinear Schrödinger equation with the fractional Laplacian, Proc. Roy. Soc. Edinburgh Sect. A, 142 (2012), 1237-1262. Google Scholar [11] N. Laskin, Fractional quantum mechanics and L'evy path integrals, Phys. Lett. A, 268 (2000), 29-305. Google Scholar [12] N. Laskin, Fractional Schrödinger equation, Phys. Rev. E, 66 (2002), 31-35. Google Scholar [13] L. Lin, Z. Liu and S. Chen, Multi-bump solutions for a semilinear Schrödinger equation, Phys. Rev. E, 58 (2009), 1659-1689. Google Scholar [14] W. Long, S. Peng and J. Yang, Infinitely many positive and sign-changing solutions for nonlinear fractional scalar field equations, Discret. Contin. Dynam. Syst., 36 (2016), 917-939. Google Scholar [15] E. S. Noussair and S. Yan, On positive multi-peak solutions of a nonlinear elliptic problem, J. Lond. Math. Soc., 62 (2000), 213-227. Google Scholar [16] E. Di Nezza, G. Palatucci and E. Valdinoci, Hitchhiker's guide to the fractional Sobolev spaces, Bull. Sci. Math., 136 (2012), 521-573. Google Scholar [17] G. Palatucci and A. Pisante, Improved sobolev embeddings, profile decomposition and concentration-compactness for fractional sobolev spaces, Calc. Var. Partial Differential Equations, 50 (2014), 799-829. Google Scholar [18] S. Secchi, Ground state solutions for nonlinear fractional Schrödinger equations in $R^N$, J. Math. Phys., 54 (2013), 031501, 17 pp. Google Scholar [19] X. Shang and J. Zhang, Concentrating solutions of nonlinear fractional Schrödinger equation with potentials, J. Differ. Equ., 258 (2015), 1106-1128. Google Scholar [20] J. Tan, The Brezis-Nirenberg type problem involving the square root of the Laplacian, Calc. Var. Partial Differential Equations, 42 (2011), 21-41. Google Scholar [21] L. Wang and C. Zhao, Infinitely many solutions to a fractional nonlinear Schrödinger equation,, arXiv:1403.0042., ().   Google Scholar
 [1] Yuxia Guo, Zhongwei Tang. Multi-bump solutions for Schrödinger equation involving critical growth and potential wells. Discrete & Continuous Dynamical Systems, 2015, 35 (8) : 3393-3415. doi: 10.3934/dcds.2015.35.3393 [2] Claudianor O. Alves, Minbo Yang. Existence of positive multi-bump solutions for a Schrödinger-Poisson system in $\mathbb{R}^{3}$. Discrete & Continuous Dynamical Systems, 2016, 36 (11) : 5881-5910. doi: 10.3934/dcds.2016058 [3] Claudianor O. Alves, Olímpio H. Miyagaki, Sérgio H. M. Soares. Multi-bump solutions for a class of quasilinear equations on $R$. Communications on Pure & Applied Analysis, 2012, 11 (2) : 829-844. doi: 10.3934/cpaa.2012.11.829 [4] Vivi Rottschäfer. Multi-bump patterns by a normal form approach. Discrete & Continuous Dynamical Systems - B, 2001, 1 (3) : 363-386. doi: 10.3934/dcdsb.2001.1.363 [5] Wulong Liu, Guowei Dai. Multiple solutions for a fractional nonlinear Schrödinger equation with local potential. Communications on Pure & Applied Analysis, 2017, 16 (6) : 2105-2123. doi: 10.3934/cpaa.2017104 [6] Xudong Shang, Jihui Zhang. Multiplicity and concentration of positive solutions for fractional nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2239-2259. doi: 10.3934/cpaa.2018107 [7] Songbai Peng, Aliang Xia. Normalized solutions of supercritical nonlinear fractional Schrödinger equation with potential. Communications on Pure & Applied Analysis, 2021, 20 (11) : 3723-3744. doi: 10.3934/cpaa.2021128 [8] D.G. deFigueiredo, Yanheng Ding. Solutions of a nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems, 2002, 8 (3) : 563-584. doi: 10.3934/dcds.2002.8.563 [9] Yinbin Deng, Wei Shuai. Sign-changing multi-bump solutions for Kirchhoff-type equations in $\mathbb{R}^3$. Discrete & Continuous Dynamical Systems, 2018, 38 (6) : 3139-3168. doi: 10.3934/dcds.2018137 [10] Masoumeh Hosseininia, Mohammad Hossein Heydari, Carlo Cattani. A wavelet method for nonlinear variable-order time fractional 2D Schrödinger equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (7) : 2273-2295. doi: 10.3934/dcdss.2020295 [11] Robert Magnus, Olivier Moschetta. The non-linear Schrödinger equation with non-periodic potential: infinite-bump solutions and non-degeneracy. Communications on Pure & Applied Analysis, 2012, 11 (2) : 587-626. doi: 10.3934/cpaa.2012.11.587 [12] Van Duong Dinh. On blow-up solutions to the focusing mass-critical nonlinear fractional Schrödinger equation. Communications on Pure & Applied Analysis, 2019, 18 (2) : 689-708. doi: 10.3934/cpaa.2019034 [13] Binhua Feng. On the blow-up solutions for the fractional nonlinear Schrödinger equation with combined power-type nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (5) : 1785-1804. doi: 10.3934/cpaa.2018085 [14] Miaomiao Niu, Zhongwei Tang. Least energy solutions for nonlinear Schrödinger equation involving the fractional Laplacian and critical growth. Discrete & Continuous Dynamical Systems, 2017, 37 (7) : 3963-3987. doi: 10.3934/dcds.2017168 [15] Nakao Hayashi, Pavel Naumkin. On the reduction of the modified Benjamin-Ono equation to the cubic derivative nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems, 2002, 8 (1) : 237-255. doi: 10.3934/dcds.2002.8.237 [16] Patricio Felmer, César Torres. Radial symmetry of ground states for a regional fractional Nonlinear Schrödinger Equation. Communications on Pure & Applied Analysis, 2014, 13 (6) : 2395-2406. doi: 10.3934/cpaa.2014.13.2395 [17] Van Duong Dinh, Binhua Feng. On fractional nonlinear Schrödinger equation with combined power-type nonlinearities. Discrete & Continuous Dynamical Systems, 2019, 39 (8) : 4565-4612. doi: 10.3934/dcds.2019188 [18] Amit Goswami, Sushila Rathore, Jagdev Singh, Devendra Kumar. Analytical study of fractional nonlinear Schrödinger equation with harmonic oscillator. Discrete & Continuous Dynamical Systems - S, 2021, 14 (10) : 3589-3610. doi: 10.3934/dcdss.2021021 [19] Miao Du, Lixin Tian. Infinitely many solutions of the nonlinear fractional Schrödinger equations. Discrete & Continuous Dynamical Systems - B, 2016, 21 (10) : 3407-3428. doi: 10.3934/dcdsb.2016104 [20] Woocheol Choi, Youngwoo Koh. On the splitting method for the nonlinear Schrödinger equation with initial data in $H^1$. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3837-3867. doi: 10.3934/dcds.2021019

2020 Impact Factor: 1.916


text:
# How to understand the storage of the Hessenberg matrix of Krylov subspace matrix?

For the Krylov subspace method to solve the large sparse linear system, we first need to generate a subspace Km = span{v,Av,...A^{m-1}v}, which indeed a process that we convert a linearly independent basis to an orthonormal basis: $$V_mAV_m = H_m,$$ where $$H_m$$ is a upper Hessenberg matrix, which has about $$m^2/2$$ nonzero entries. So, when we code in matlab, we first need to H = zeros(m,m), so in fact, we need to store all the $$m^2$$ entries including the zero entries. But in many books, the author said the storage of the matrix $$H_m$$ is about $$m^2/2$$. I do not understand why author said that? Because the code H = zeros(m,m) indeed store $$m^2$$ entries even though $$m^2/2$$ zero entries. any suggestions?

• You can of course use a data structure that really only stores the upper half of the matrix, at a memory cost of roughly $m^2/2$. The fact that you call zeros(m,m) and get a matrix that also has memory allocated for everything below the diagonal is your choice. It is not necessary for the algorithm. – Wolfgang Bangerth Feb 5 at 2:56
• @WolfgangBangerth, Thanks Prof. I get your comment. I know it is not necessary. But If one uses zeros(m,m), then it stores all the memory. And in fact, this is the more common way that we use, because most people uses matlab to code the algorithm. And I also found that some authors states that we need to store $m^2/2$ memory in his book, but he also called zeros(m,m), because he uses matlab to do the algorithm. So, I am sometimes a little confused. So, if we state that the memory is $m^2/2$, then we should not call zeros(m,m), i.e., we cannot choose matlab to do this, right? – sunshine Feb 5 at 3:19
• So then don't use matlab, or if you use matlab, use a better suited data structure. It's like saying "Some authors state that it takes 3 hours to get from Austin, TX to Houston TX, but when I ride my bike it takes all day", to which the answer is "Then don't take the bike, take a car!" Just because you don't use the right tool for a task doesn't invalidate the statement that it only takes $m^2/2$ memory :-) – Wolfgang Bangerth Feb 5 at 13:08
• @WolfgangBangerth, an interesting comment, Get it. it is just because we donot use the right tool, haha, thanks very much. ;) – sunshine Feb 7 at 3:13
• No, to be precise, it's because you don't use the right tool ;-) In professional implementations, we actually do often only store the nonzero entries ;-)) – Wolfgang Bangerth Feb 7 at 4:15

Matlab often does not care about these sorts of optimizations. Another classical example is QR factorization, where it returns the full Q matrix instead of a compact representation that could use about $$n^2/2$$ storage. Or LU factorizations, where two separate matrices L and U are returned for simplicity. Factorizations are computed in new matrices and not in-place overwriting the inputs.
In practice I don't think that particular factor of $$2$$ is worth pursuing. Thinking of gmres applied to a large problem ($$n >> m$$), the $$m^2$$ storage of that small Hessenberg projection is dwarfed by the $$m\cdot n$$ storage of the search vectors themselves (the $$\mathbf V_m$$). You are forced into restarts because $$\mathbf V_m$$ is too big, not because of $$\mathbf H_m$$.
• Thanks very much. a question is that in your comments, a large problems (m>>n), it seems wrong, it should be (m < < n), because m is the dimension of the Krylov subspace, and n is the system size, right? – sunshine Feb 5 at 2:28
• Usually, I like the convention that $m>n$ because $m$ has three legs and $n$ has two. And because it is consistent with the notation from graph theory that $m=|E|$, $n = |V|$. – Federico Poloni Feb 5 at 13:19
• @FedericoPoloni, an interesting idea that I never heard. m has 3 legs, :) I like this. Thanks very much. – sunshine Feb 7 at 3:10


text:
August 29th, 2017

# Floating Point Visually Explained

In the early 90s, to write a 3D game engine for PCs largely meant to repurpose the machine. PCs of this era were built to run word processors and spreadsheets, not perform 3D calculations at 70 frames per second. A significant obstacle was the CPU which despite being powerful did not have an hardware floating point unit. Programmers only had an ALU available to crunch integers.

As I was writing Game Engine Black Book: Wolfenstein 3D (ebook) I wanted to vividly demonstrate how much of a handicap it was to work without floating points. My personal attempts at understanding floating points using canonical articles were met with significant resistance from my brain. I tried to find a different way. Something far from $(-1)^S * 1.M * 2^{(E-127)}$ and its mysterious exponent/mantissa. Possibly a drawing since they seem to flow through my brain effortlessly.

I ended up with what follows and I decided to include it in the book. I am not claiming this is my invention but I have never seen floating points explained this way so far. I hope it will helps a few people like me who are a bit allergic to mathematic notations.

### How Floating Point are usually explained

As David Goldbert wrote:

Floating-point arithmetic is considered an esoteric subject by many people.

I could not agree more with him. Yet it is important to understand how it works in order to fully grasp how useful it is to program a 3D engine. In the C language, floats are 32 bits container following the IEEE 754 standard. Their purpose is to store and allow operations on approximation of real numbers. The way I have seen them explained so far is as follow. The 32 bits are divided in three sections:
• 1 bit S for the sign
• 8 bits E for the exponent
• 23 bits for the mantissa

Floating Point internals.

The three sections of a floating Point number.

So far, so good. Now, how numbers are interpreted is usually explained with the formula:

$$(-1)^S * 1.M * 2^{(E-127)}$$

How everybody hates floating point to be explained to them.

This is usually where I flip the table. Maybe I am allergic to mathematic notation but something just doesn't click in my brain when I read this. It feels like learning to draw a owl:

### A different way to explain...

Although correct, this way of explaining floating point usually leaves some of us completely clueless. I blame this dreadful notation for discouraging legions of programmers, scaring them to the point where they never looked back to understand how floating point actually works. Fortunately, there is a different way to explain it. Instead of Exponent, think of a Window between two consecutive power of two integers. Instead of a Mantissa, think of an Offset within that window.

The three sections of a Floating Point number.

The window tells within which two consecutive power-of-two the number will be: [0.5,1], [1,2], [2,4], [4,8] and so on (up to [$2^{127}$,$2^{128}$]. The offset divides the window in $2^{23} = 8388608$ buckets. With the window and the offset you can approximate a number. The window is an excellent mechanism to protect from overflowing. Once you have reached the maximum in a window (e.g [2,4]), you can "float" it right and represent the number within the next window (e.g [4,8]). It only costs a little bit of precision since the window becomes twice as large.

Trivia : How much precision is lost when the window covers a wider range? Let's take an example with window [1,2] where the 8388608 offsets cover a range of 1 which gives a precision of $\frac{(2-1)}{8388608}=0.00000011920929$. In the window [2048,4096] the 8388608 offsets cover a range of $(4096-2048) = 2048$ which gives a precision $\frac{(4096-2048)}{8388608}=0.0002$.

The next figure illustrates how the number 6.1 would be encoded. The window must start at 4 and span to next power of two, 8. The offset is about half way down the window.

Value 6.1 approximated with floating point

Let's take an other example with the detailed calculations of the floating point representation of a number we all know well: 3.14.

• The number 3.14 is positive $\rightarrow S=0$.
• The number 3.14 is between the power of two 2 and 4 so the floating window must start at $2^1$ $\rightarrow E=128$ (see formula where window is $2^{(E-127)}$).
• Finally there are $2^{23}$ offsets available to express where 3.14 falls within the interval [2-4]. It is at $\frac{3.14 -2 }{4 - 2} = 0.57$ within the interval which makes the offset $M = 2^{23}*0.57 = 4781507$

Which in binary translates to:

• S = 0 = 0b
• E = 128 = 10000000b
• M = 4781507 = 10010001111010111000011b

3.14 floating point binary representation.

The value 3.14 is therefore approximated to 3.1400001049041748046875.
The corresponding value with the ugly formula:

$$3.14 = (-1)^0 * 1.57 * 2^{(128-127)}$$

And finally the graphic representation with window and offset:

3.14 window and offset.

Trivia : Since floating point units were so slow, why did the C language end up with float and double types ? After all, the machine used to invent the language (PDP-11) did not have a floating point unit! The manufacturer (DEC) had promised to Dennis Ritchie and Ken Thompson the next model would have one. Being astronomy enthusiasts they decided to add those two types to their language.

Trivia : People who really wanted a hardware floating point unit in 1991 could buy one. The only people who could possibly want one back then would have been scientists (as per Intel understanding of the market). They were marketed as "Math CoProcessor". Performance were average and price was outrageous (200 USD in 1993 equivalent to 350 USD in 2016.). As a result, sales were mediocre.

I hope that helped :) !