text:
## Stability and oscillations of numerical solutions for differential equations with piecewise continuous arguments of alternately advanced and retarded type.(English)Zbl 1207.65103

The authors study a differential equation with alternately argument of the form
$x'(t) = a x(t) + b x( [t+1/2]), \quad t>0$
$x (0) = x_{0},$
where $$a,b,x_{0}$$ are real constants and [.] denotes the greatest integer function. Using the weighted difference method to solve this problem, conditions of stability and oscillations (for analytical and numerical solutions ) are presented in dependence of coefficients $$a , b$$.

### MSC:

 65L20 Stability and convergence of numerical methods for ordinary differential equations 34K11 Oscillation theory of functional-differential equations 34K20 Stability theory of functional-differential equations 34K28 Numerical approximation of solutions of functional-differential equations (MSC2010) 65L03 Numerical methods for functional-differential equations 65L05 Numerical methods for initial value problems involving ordinary differential equations 65L07 Numerical investigation of stability of solutions to ordinary differential equations
Full Text:

### References:

 [1] Wiener, J., Differential equations with piecewise constant delays, (), 547-552 [2] Shah, S.M.; Wiener, J., Advanced differential equations with piecewise constant argument deviations, Int. J. math. math. sci., 6, 671-703, (1983) · Zbl 0534.34067 [3] Cooke, K.L.; Wiener, J., Retarded differential equations with piecewise constant delays, J. math. anal. appl., 99, 265-297, (1984) · Zbl 0557.34059 [4] Busenberg, S.; Cooke, K., () [5] Küpper, T.; Yuang, R., On quasi-periodic solutions of differential equations with piecewise constant argument, J. math. anal. appl., 267, 173-193, (2002) · Zbl 1008.34063 [6] Akhmet, M.U.; Büyükadal, C., Differential equations with state-dependent piecewise constant argument, Nonlinear anal., 72, 4200-4210, (2010) · Zbl 1195.34103 [7] Muroya, Y., New contractivity condition in a population model with piecewise constant arguments, J. math. anal. appl., 346, 65-81, (2008) · Zbl 1161.34048 [8] Bainov, D.; Kostadinov, T.; Petrov, V., Oscillatory and asymptotic properties of nonlinear first order neutral differential equations with piecewise constant argument, J. math. anal. appl., 194, 612-639, (1995) · Zbl 0842.34070 [9] Hong, J.; Obaya, R.; Sanz, A., Almost periodic type solutions of differential equations with piecewise constant argument, Nonlinear anal., 45, 661-668, (2001) · Zbl 0996.34062 [10] Wiener, J.; Cooke, K.L., Oscillations in systems of differential equations with piecewise constant argument, J. math. anal. appl., 137, 221-239, (1989) · Zbl 0728.34077 [11] Wang, G.Q., Periodic solutions of a neutral differential equation with piecewise constant arguments, J. math. anal. appl., 326, 736-747, (2007) · Zbl 1113.34053 [12] Akhmet, M.U., Stability of differential equations with piecewise constant arguments of generalized type, Nonlinear anal., 68, 794-803, (2008) · Zbl 1173.34042 [13] Wiener, J., Generalized solutions of functional differential equations, (1993), World Scientific Singapore · Zbl 0874.34054 [14] Aftabizadeh, A.R.; Wiener, J.; Xu, J.M., Oscillatory and periodic solutions of delay differential equations with piecewise constant argument, Proc. amer. math. soc., 99, 673-679, (1987) · Zbl 0631.34078 [15] Cooke, K.L.; Wiener, J., An equation alternately of retarded and advanced type, Proc. amer. math. soc., 99, 726-732, (1987) · Zbl 0628.34074 [16] Seifert, G., Almost periodic solutions of certain differential equations with piecewise constant delays and almost periodic time dependence, J. differential equations, 164, 451-458, (2000) · Zbl 1009.34064 [17] Yang, P.; Liu, Y.; Ge, W., Green’s function for second order differential equations with piecewise constant argument, Nonlinear anal., 64, 1812-1830, (2006) · Zbl 1111.34048 [18] Akhmet, M.U., Integral manifolds of differential equations with piecewise constant argument of generalized type, Nonlinear anal., 66, 367-383, (2007) · Zbl 1122.34054 [19] Shen, J.H.; Stavroulakis, I.P., Oscillatory and nonoscillatory delay equations with piecewise constant argument, J. math. anal. appl., 248, 385-401, (2000) · Zbl 0966.34063 [20] Liu, M.Z.; Song, M.H.; Yang, Z.W., Stability of runge – kutta methods in the numerical solution of equation $$u^\prime(t) = a u(t) + a_0 u([t])$$, J. comput. appl. math., 166, 361-370, (2004) · Zbl 1052.65070 [21] Song, M.H.; Yang, Z.W.; Liu, M.Z., Stability of $$\theta$$-methods for advanced differential equations with piecewise continuous arguments, Comput. math. appl., 49, 1295-1301, (2005) · Zbl 1082.65078 [22] Lv, W.J.; Yang, Z.W.; Liu, M.Z., Stability of runge – kutta methods for the alternately advanced and retarded differential equations with piecewise continuous arguments, Comput. math. appl., 54, 326-335, (2007) · Zbl 1140.65057 [23] Yang, Z.W.; Liu, M.Z.; Nieto, J.J., Runge – kutta methods for first-order periodic boundary value differential equations with piecewise constant arguments, J. comput. appl. math., 233, 990-1004, (2009) · Zbl 1180.65094 [24] Liu, M.Z.; Gao, J.F.; Yang, Z.W., Oscillation analysis of numerical solution in the $$\theta$$-methods for equation $$x^\prime(t) + a x(t) + a_1 x([t - 1]) = 0$$, Appl. math. comput., 186, 566-578, (2007) · Zbl 1118.65080 [25] Liu, M.Z.; Gao, J.F.; Yang, Z.W., Preservation of oscillations of the runge – kutta method for equation $$x^\prime(t) + a x(t) + a_1 x([t - 1]) = 0$$, Comput. math. appl., 58, 1113-1125, (2009) · Zbl 1189.65143 [26] Aftabizadeh, A.R.; Wiener, J., Oscillatory and periodic solutions of an equation alternately of retarded and advanced type, Appl. anal., 23, 219-231, (1986) · Zbl 0598.34059
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:
# A titration neutralizes 25mL of an unknown acid using 32 mL of 6.0 M KOH. What is the molarity of the unknown acid in the original solution?

$\left[\left(M o l a r i t y A c i d\right) \left(V o l u m e A c i d\right)\right] = \left[\left(M o l a r i t y B a s e\right) \left(V o l u m e B a s e\right)\right]$
$\left(M o l a r i t y A c i d\right) \left(25 m l\right) = \left(6.0 M\right) \left(32 m l\right)$
$M o l a r i t y A c i d = \frac{\left(6.0 M\right) \left(32 m l\right)}{\left(25 m l\right)} = 7.68 M$

format: plain


text:
What does it mean to model expression data by a probability distribution?
1
2
Entering edit mode
3.9 years ago

I have very frequently seen in the papers, lecture notes etc. that RNA-Seq data can be modeled by a Poisson distribution, and microarray data can be modeled by a Gaussian distribution, and I haven't given much thought on that. But I recently realized that I don't really understand what that means. Let's say we have a 100 x 20K matrix of RNA-Seq counts where rows represent samples (say, lung cancer patients) and columns represent genes. Then, do we assume that the set of 100 values in each column (gene) would follow a Poisson distribution? Or do we assume that the set of 20K values in each row follows a Poisson distribution? Or, each gene-sample pair is distributed by a separate Poisson with a separate mean? If the last is true, then we have no idea how to compute the mean and variance of those 2 million different distributions, because we have only a single value from each of them.

Also, I have seen many papers where the microarray data is modeled by a p-variate Gaussian distribution where p is the number of genes, although it looks like microarray data is usually assumed to be distributed by a univariate Gaussian. What is the reason behind the multivariate assumption? Does multivariate Gaussian lead to a more accurate modeling of the data?

As you can see, I am totally confused. Can someone explain those in an intuitive and least technical way possible (I am not a statistician)?

RNA-Seq distribution microarray • 1.6k views
3
Entering edit mode
3.9 years ago

Modeling data by a distribution simply means we assume that the numbers come from this distribution. In the case of RNA seq, the read counts are assumed to follow a Poisson distribution. See this post for more on this. For microarray data, the cleaned-up, log-transformed expression levels are often assumed to be Normally-distributed. At the gene level, when the expression is the average over many spots (for some arrays) or samples, the mean tends towards a Gaussian distribution due to the central limit theorem. These are usually simplifying assumptions that make dealing with the data easier. Most of the time, real data have long tails or are over/under-dispersed compared to standard distributions.

0
Entering edit mode

So, relating this to my actual question, are you saying that each column (gene) in the example I gave is distributed by a Gaussian distribution? Why not each row (sample)?

0
Entering edit mode

A sample x gene matrix represents the measured expression levels of the genes in each sample. Depending on how this results was arrived at, each value can be seen as being generated by a Gaussian distribution or even as the mean of such a distribution. In such cases, the rows (samples) can be modeled by a multivariate Gaussian composed of the distributions of all the genes. There is no reason to assume the values in rows/columns to be drawn from the same distribution. If you assume that each row (sample) can be modeled by just one Gaussian, then on average, all genes would have the same expression level. If each column (gene) is modeled by one distribution then each gene will have on average the same expression level in each sample.


text:
# Properties

 Label 140.2.q.b Level $140$ Weight $2$ Character orbit 140.q Analytic conductor $1.118$ Analytic rank $0$ Dimension $4$ CM no Inner twists $2$

# Related objects

## Newspace parameters

 Level: $$N$$ $$=$$ $$140 = 2^{2} \cdot 5 \cdot 7$$ Weight: $$k$$ $$=$$ $$2$$ Character orbit: $$[\chi]$$ $$=$$ 140.q (of order $$6$$, degree $$2$$, minimal)

## Newform invariants

 Self dual: no Analytic conductor: $$1.11790562830$$ Analytic rank: $$0$$ Dimension: $$4$$ Relative dimension: $$2$$ over $$\Q(\zeta_{6})$$ Coefficient field: $$\Q(\sqrt{-3}, \sqrt{-19})$$ Defining polynomial: $$x^{4} - x^{3} - 4 x^{2} - 5 x + 25$$ Coefficient ring: $$\Z[a_1, \ldots, a_{5}]$$ Coefficient ring index: $$1$$ Twist minimal: yes Sato-Tate group: $\mathrm{SU}(2)[C_{6}]$

## $q$-expansion

Coefficients of the $$q$$-expansion are expressed in terms of a basis $$1,\beta_1,\beta_2,\beta_3$$ for the coefficient ring described below. We also show the integral $$q$$-expansion of the trace form.

 $$f(q)$$ $$=$$ $$q + ( 2 - \beta_{2} ) q^{3} + ( -1 + \beta_{1} - \beta_{3} ) q^{5} + ( 1 + \beta_{1} - \beta_{2} ) q^{7} +O(q^{10})$$ $$q + ( 2 - \beta_{2} ) q^{3} + ( -1 + \beta_{1} - \beta_{3} ) q^{5} + ( 1 + \beta_{1} - \beta_{2} ) q^{7} + ( 1 - 2 \beta_{1} + \beta_{2} + \beta_{3} ) q^{11} + ( 2 - 2 \beta_{1} - 2 \beta_{2} + 2 \beta_{3} ) q^{13} + ( -2 + 2 \beta_{1} + \beta_{2} - \beta_{3} ) q^{15} + ( -3 + \beta_{2} - \beta_{3} ) q^{17} + ( -1 + \beta_{1} - 2 \beta_{3} ) q^{19} + ( 1 + \beta_{1} - 2 \beta_{2} + \beta_{3} ) q^{21} + ( 3 - 2 \beta_{1} + \beta_{2} ) q^{23} + ( -4 - \beta_{1} + \beta_{3} ) q^{25} + ( -3 + 6 \beta_{2} ) q^{27} + ( -1 + \beta_{1} + \beta_{2} + \beta_{3} ) q^{29} + ( -1 + 2 \beta_{1} + \beta_{2} - \beta_{3} ) q^{31} + ( 3 - 3 \beta_{1} ) q^{33} + ( -6 + \beta_{1} + 6 \beta_{2} ) q^{35} + ( -5 + \beta_{1} - 4 \beta_{2} ) q^{37} + ( 2 - 4 \beta_{1} - 4 \beta_{2} + 2 \beta_{3} ) q^{39} + ( -7 - \beta_{1} - \beta_{2} - \beta_{3} ) q^{41} + ( 3 - \beta_{1} - 5 \beta_{2} + \beta_{3} ) q^{43} + ( 3 - \beta_{1} + 2 \beta_{2} ) q^{47} + ( 4 \beta_{2} + 3 \beta_{3} ) q^{49} + ( -5 + \beta_{1} + 4 \beta_{2} - 2 \beta_{3} ) q^{51} + ( 1 + \beta_{2} + 3 \beta_{3} ) q^{53} + ( 9 + \beta_{1} - 6 \beta_{2} - 2 \beta_{3} ) q^{55} + ( -2 + 3 \beta_{1} + \beta_{2} - 3 \beta_{3} ) q^{57} + ( -1 + 2 \beta_{1} + \beta_{2} - \beta_{3} ) q^{59} + ( 5 + 2 \beta_{1} - 7 \beta_{2} - 4 \beta_{3} ) q^{61} + ( 8 + 2 \beta_{1} + 2 \beta_{2} ) q^{65} + ( 6 - \beta_{2} + 4 \beta_{3} ) q^{67} + ( 7 - 2 \beta_{1} - 2 \beta_{2} - 2 \beta_{3} ) q^{69} + ( 2 + 2 \beta_{1} + 2 \beta_{2} + 2 \beta_{3} ) q^{71} + ( 5 - 3 \beta_{2} - \beta_{3} ) q^{73} + ( -8 - 2 \beta_{1} + 4 \beta_{2} + \beta_{3} ) q^{75} + ( 7 - 11 \beta_{2} - 3 \beta_{3} ) q^{77} + ( 3 + \beta_{1} - 4 \beta_{2} - 2 \beta_{3} ) q^{79} + 9 \beta_{2} q^{81} + ( -1 + 3 \beta_{1} - \beta_{2} - 3 \beta_{3} ) q^{83} + ( 3 - 3 \beta_{1} - 6 \beta_{2} + 2 \beta_{3} ) q^{85} + ( -1 + 2 \beta_{2} + 3 \beta_{3} ) q^{87} + ( -7 + 7 \beta_{2} ) q^{89} + ( 10 - 4 \beta_{1} - 12 \beta_{2} + 2 \beta_{3} ) q^{91} + ( -1 + 3 \beta_{1} + 2 \beta_{2} ) q^{93} + ( -4 - \beta_{1} - 5 \beta_{2} + \beta_{3} ) q^{95} + ( -4 + 8 \beta_{2} ) q^{97} +O(q^{100})$$ $$\operatorname{Tr}(f)(q)$$ $$=$$ $$4 q + 6 q^{3} - 2 q^{5} + 3 q^{7} + O(q^{10})$$ $$4 q + 6 q^{3} - 2 q^{5} + 3 q^{7} + 3 q^{11} - 3 q^{15} - 9 q^{17} - q^{19} + 12 q^{23} - 18 q^{25} - 2 q^{29} + q^{31} + 9 q^{33} - 11 q^{35} - 27 q^{37} - 6 q^{39} - 30 q^{41} + 15 q^{47} + 5 q^{49} - 9 q^{51} + 3 q^{53} + 27 q^{55} + q^{59} + 12 q^{61} + 38 q^{65} + 18 q^{67} + 24 q^{69} + 12 q^{71} + 15 q^{73} - 27 q^{75} + 9 q^{77} + 7 q^{79} + 18 q^{81} - 5 q^{85} - 3 q^{87} - 14 q^{89} + 10 q^{91} + 3 q^{93} - 28 q^{95} + O(q^{100})$$

Basis of coefficient ring in terms of a root $$\nu$$ of $$x^{4} - x^{3} - 4 x^{2} - 5 x + 25$$:

 $$\beta_{0}$$ $$=$$ $$1$$ $$\beta_{1}$$ $$=$$ $$\nu$$ $$\beta_{2}$$ $$=$$ $$($$$$\nu^{3} + 4 \nu^{2} - 4 \nu - 5$$$$)/20$$ $$\beta_{3}$$ $$=$$ $$($$$$-\nu^{3} + 4 \nu + 5$$$$)/4$$
 $$1$$ $$=$$ $$\beta_0$$ $$\nu$$ $$=$$ $$\beta_{1}$$ $$\nu^{2}$$ $$=$$ $$\beta_{3} + 5 \beta_{2}$$ $$\nu^{3}$$ $$=$$ $$-4 \beta_{3} + 4 \beta_{1} + 5$$

## Character values

We give the values of $$\chi$$ on generators for $$\left(\mathbb{Z}/140\mathbb{Z}\right)^\times$$.

 $$n$$ $$57$$ $$71$$ $$101$$ $$\chi(n)$$ $$-1$$ $$1$$ $$-1 + \beta_{2}$$

## Embeddings

For each embedding $$\iota_m$$ of the coefficient field, the values $$\iota_m(a_n)$$ are shown below.

For more information on an embedded modular form you can click on its label.

Label $$\iota_m(\nu)$$ $$a_{2}$$ $$a_{3}$$ $$a_{4}$$ $$a_{5}$$ $$a_{6}$$ $$a_{7}$$ $$a_{8}$$ $$a_{9}$$ $$a_{10}$$
9.1
 −1.63746 − 1.52274i 2.13746 + 0.656712i 2.13746 − 0.656712i −1.63746 + 1.52274i
0 1.50000 0.866025i 0 −0.500000 2.17945i 0 −1.13746 2.38876i 0 0 0
9.2 0 1.50000 0.866025i 0 −0.500000 + 2.17945i 0 2.63746 0.209313i 0 0 0
109.1 0 1.50000 + 0.866025i 0 −0.500000 2.17945i 0 2.63746 + 0.209313i 0 0 0
109.2 0 1.50000 + 0.866025i 0 −0.500000 + 2.17945i 0 −1.13746 + 2.38876i 0 0 0
 $$n$$: e.g. 2-40 or 990-1000 Significant digits: Format: Complex embeddings Normalized embeddings Satake parameters Satake angles

## Inner twists

Char Parity Ord Mult Type
1.a even 1 1 trivial
35.j even 6 1 inner

## Twists

By twisting character orbit
Char Parity Ord Mult Type Twist Min Dim
1.a even 1 1 trivial 140.2.q.b yes 4
3.b odd 2 1 1260.2.bm.b 4
4.b odd 2 1 560.2.bw.a 4
5.b even 2 1 140.2.q.a 4
5.c odd 4 2 700.2.i.f 8
7.b odd 2 1 980.2.q.b 4
7.c even 3 1 140.2.q.a 4
7.c even 3 1 980.2.e.f 4
7.d odd 6 1 980.2.e.c 4
7.d odd 6 1 980.2.q.g 4
15.d odd 2 1 1260.2.bm.a 4
20.d odd 2 1 560.2.bw.e 4
21.h odd 6 1 1260.2.bm.a 4
28.g odd 6 1 560.2.bw.e 4
35.c odd 2 1 980.2.q.g 4
35.i odd 6 1 980.2.e.c 4
35.i odd 6 1 980.2.q.b 4
35.j even 6 1 inner 140.2.q.b yes 4
35.j even 6 1 980.2.e.f 4
35.k even 12 2 4900.2.a.bf 4
35.l odd 12 2 700.2.i.f 8
35.l odd 12 2 4900.2.a.be 4
105.o odd 6 1 1260.2.bm.b 4
140.p odd 6 1 560.2.bw.a 4

By twisted newform orbit
Twist Min Dim Char Parity Ord Mult Type
140.2.q.a 4 5.b even 2 1
140.2.q.a 4 7.c even 3 1
140.2.q.b yes 4 1.a even 1 1 trivial
140.2.q.b yes 4 35.j even 6 1 inner
560.2.bw.a 4 4.b odd 2 1
560.2.bw.a 4 140.p odd 6 1
560.2.bw.e 4 20.d odd 2 1
560.2.bw.e 4 28.g odd 6 1
700.2.i.f 8 5.c odd 4 2
700.2.i.f 8 35.l odd 12 2
980.2.e.c 4 7.d odd 6 1
980.2.e.c 4 35.i odd 6 1
980.2.e.f 4 7.c even 3 1
980.2.e.f 4 35.j even 6 1
980.2.q.b 4 7.b odd 2 1
980.2.q.b 4 35.i odd 6 1
980.2.q.g 4 7.d odd 6 1
980.2.q.g 4 35.c odd 2 1
1260.2.bm.a 4 15.d odd 2 1
1260.2.bm.a 4 21.h odd 6 1
1260.2.bm.b 4 3.b odd 2 1
1260.2.bm.b 4 105.o odd 6 1
4900.2.a.be 4 35.l odd 12 2
4900.2.a.bf 4 35.k even 12 2

## Hecke kernels

This newform subspace can be constructed as the kernel of the linear operator $$T_{3}^{2} - 3 T_{3} + 3$$ acting on $$S_{2}^{\mathrm{new}}(140, [\chi])$$.

## Hecke characteristic polynomials

$p$ $F_p(T)$
$2$ $$T^{4}$$
$3$ $$( 3 - 3 T + T^{2} )^{2}$$
$5$ $$( 5 + T + T^{2} )^{2}$$
$7$ $$49 - 21 T + 2 T^{2} - 3 T^{3} + T^{4}$$
$11$ $$144 + 36 T + 21 T^{2} - 3 T^{3} + T^{4}$$
$13$ $$256 + 44 T^{2} + T^{4}$$
$17$ $$4 + 18 T + 29 T^{2} + 9 T^{3} + T^{4}$$
$19$ $$196 - 14 T + 15 T^{2} + T^{3} + T^{4}$$
$23$ $$49 + 84 T + 41 T^{2} - 12 T^{3} + T^{4}$$
$29$ $$( -14 + T + T^{2} )^{2}$$
$31$ $$196 + 14 T + 15 T^{2} - T^{3} + T^{4}$$
$37$ $$3136 + 1512 T + 299 T^{2} + 27 T^{3} + T^{4}$$
$41$ $$( 42 + 15 T + T^{2} )^{2}$$
$43$ $$196 + 47 T^{2} + T^{4}$$
$47$ $$196 - 210 T + 89 T^{2} - 15 T^{3} + T^{4}$$
$53$ $$1764 + 126 T - 39 T^{2} - 3 T^{3} + T^{4}$$
$59$ $$196 + 14 T + 15 T^{2} - T^{3} + T^{4}$$
$61$ $$441 + 252 T + 165 T^{2} - 12 T^{3} + T^{4}$$
$67$ $$2401 + 882 T + 59 T^{2} - 18 T^{3} + T^{4}$$
$71$ $$( -48 - 6 T + T^{2} )^{2}$$
$73$ $$196 - 210 T + 89 T^{2} - 15 T^{3} + T^{4}$$
$79$ $$4 + 14 T + 51 T^{2} - 7 T^{3} + T^{4}$$
$83$ $$1764 + 87 T^{2} + T^{4}$$
$89$ $$( 49 + 7 T + T^{2} )^{2}$$
$97$ $$( 48 + T^{2} )^{2}$$


text:
# Can we deduce that the equation $f(x)=0$ has finite number of solutions in the interval $(-∞,2)$?

Let us consider an equation $f(x)=0$ where $f$ is a real analytic function. Assume that this equation has still a finite number of solutions in any interval of the form $(y,2)$ where the number $y<2$ is located in an infinite discrete set. Can we deduce that the equation $f(x)=0$ has finite number of solutions in the interval $(-∞,2)$

• What we can deduce is that the number of the solutions of $f(x)=0$ is not uncountable – clark Aug 23 '13 at 20:30
• @clark: I add the fcat that $f$ is analytic. – Germany Aug 24 '13 at 6:47

A very simple counterexample is $f(x)=\sin x$.


text:
# lifetab

0th

Percentile

##### Create cohort life table

Create cohort life table.

Keywords
manip
##### Usage
lifetab(tis, ninit, nlost, nevent)
##### Arguments
tis
a vector of end points of time intervals, whose length is 1 greater than nlost and nevent.
ninit
the number of subjects initially entering the study.
nlost
a vector of the number of individuals lost follow or withdrawn alive for whatever reason.
nevent
a vector of the number of individuals who experienced the event
##### Value

A data.frame with the following columns:
nsubs
the number of subject entering the intervals who have not experienced the event.
nlost
the number of individuals lost follow or withdrawn alive for whatever reason.
nrisk
the estimated number of individuals at risk of experiencing the event.
nevent
the number of individuals who experienced the event.
surv
the estimated survival function at the start of the intervals.
pdf
the estimated probability density function at the midpoint of the intervals.
hazard
the estimated hazard rate at the midpoint of the intervals.
se.surv
the estimated standard deviation of survival at the beginning of the intervals.
se.pdf
the estimated standard deviation of the prbability density function at the midpoint of the intervals.
se.hazard
the estimated standard deviation of the hazard function at the midpoint of the intervals
The row.names are the intervals.

• lifetab
##### Examples
tis <- c(0, 2, 3, 5, 7, 11, 17, 25, 37, 53, NA)
nsubs <- c(927, 848, 774, 649, 565, 449, 296, 186, 112, 27)
nlost <- c(2, 3, 6, 9, 7, 5, 3, rep(0, 3))
nevent <- c(77, 71, 119, 75, 109, 148, 107, 74, 85, 27)

lifetab(tis, nsubs[1], nlost, nevent)

Documentation reproduced from package KMsurv, version 0.1-5, License: GPL (>= 3)

### Community examples

Looks like there are no examples yet.


text:
×

# Root problem

How to square root a fraction in LaTex?

Like this:

The picture taken from here

Note by Munem Sahariar
3 months ago

Sort by:

- 3 months ago

The link is invalid. You have to use https not hhttp.

- 3 months ago

Oh, sorry. I guess I miscopied XD

- 3 months ago

Here's how to write it: \sqrt { \frac { a }{ b } }

- 3 months ago

After knowing it, I have added this code to the discussion LaTex guide

- 3 months ago

- 3 months ago

Thanks, this works $$\sqrt { \dfrac { a }{ b } }$$.

- 3 months ago


text:
# SHM Math Explodes (Req: help finding Real parts)

1. Feb 16, 2009

### malweth

1. The problem statement, all variables and given/known data
I'm not attempting a specific problem, I'm just trying to find a correct way of doing the math behind simple harmonic motion ODEs...

The example problem I've given myself (based on the books I'm using) is a dashpot with constant $$c$$, spring with constant $$k$$ and a mass $$m$$.

Specifically, I'm trying to understand the energy lost by the dashpot, but I'm in the "Calculus" subforum for a reason:

2. Relevant equations

(variables $$/dt$$)
$$m\ddot x + c\dot x + kx = 0$$ - (Unforced, damped SHM).
which is eqivalent to:
$$\ddot x + \gamma\dot x + \omega_0^2 x = 0$$

The solution is
$$x = \hat A e^{\alpha t}$$ and is differentiated & substituted back in to get:

$$\alpha^2 + \gamma\alpha + \omega_0^2 = 0$$

which is easy to solve for alpha:

$$\alpha = -\gamma / 2 \pm j\sqrt{\omega_0^2 - \gamma^2/4}$$

3. The attempt at a solution
The problem I have is in substituting back in... at first it's not too bad, but I'm trying to get real values out... even with letting $$\omega_r = \sqrt{\omega_0^2 - \gamma^2/4}$$ it gets complicated quickly in my pen & paper scratches...

$$x = \hat A e^{-\gamma/2}(e^{j\omega_r t} + e^{-j\omega_r t})$$

gets differentiated to find velocity (making it more complicated, but manageable), and then "de-Eulered" to find a real part. Am I doing something wrong? I don't see anything half as complicated in the books I'm using (primary book is "Fundamentals of Acoustics," by Kinsler and my additional resource is from Feynman's first volume on physics).

The books make it seem as though I'm doing something wrong, but I can't find how. Any help would be appreciated!

2. Feb 16, 2009

### Tom Mattson

Staff Emeritus
This is wrong. You've lost the decaying exponential part. Also, you only have one constant of integration. In a 2nd order ODE you must have 2 constants of integration in your general solution.

It should be:

$$x(t)=e^{-\gamma t/2}\left(Ae^{j\omega_rt}+Be^{-j\omega_rt}\right)$$

3. Feb 16, 2009

### malweth

Thanks! I forgot about the other constant. The missing $$t$$ value in the exponent was a mistype.

Am I otherwise doing things correctly when trying to get back into real space (for Energy calculations)?

4. Feb 16, 2009

### Tom Mattson

Staff Emeritus
It looks to me like you are.

5. Feb 16, 2009

### malweth

great! Thanks for the help.


text:
# Compute Thermal Expansion Eigenstrain Beam

Computes eigenstrain due to thermal expansion with a constant coefficient

## Description

ComputeBeamThemalExpansionEigenstrain calculates the thermal strain due to a change in temperature (from the stress-free temperature) using a constant thermal expansion coefficient. This thermal strain is applied only along the axial direction of the beam.

## Example Input File Syntax

[./thermal]
type = ComputeThermalExpansionEigenstrainBeam
thermal_expansion_coeff = 1e-4
temperature = 100
stress_free_temperature = 0
eigenstrain_name = thermal
[../]

(modules/tensor_mechanics/test/tests/beam/eigenstrain/thermal_expansion_small.i)

## Input Parameters

• stress_free_temperatureReference temperature at which there is no thermal expansion for thermal eigenstrain calculation

C++ Type:std::vector

Options:

Description:Reference temperature at which there is no thermal expansion for thermal eigenstrain calculation

• temperatureCoupled temperature

C++ Type:std::vector

Options:

Description:Coupled temperature

• eigenstrain_nameMaterial property name for the eigenstrain vector computed by this model. IMPORTANT: The name of this property must also be provided to the strain calculator.

C++ Type:std::string

Options:

Description:Material property name for the eigenstrain vector computed by this model. IMPORTANT: The name of this property must also be provided to the strain calculator.

### Required Parameters

• thermal_expansion_coeffThermal expansion coefficient

C++ Type:double

Options:

Description:Thermal expansion coefficient

• computeTrueWhen false, MOOSE will not call compute methods on this material. The user must call computeProperties() after retrieving the Material via MaterialPropertyInterface::getMaterial(). Non-computed Materials are not sorted for dependencies.

Default:True

C++ Type:bool

Options:

Description:When false, MOOSE will not call compute methods on this material. The user must call computeProperties() after retrieving the Material via MaterialPropertyInterface::getMaterial(). Non-computed Materials are not sorted for dependencies.

• boundaryThe list of boundary IDs from the mesh where this boundary condition applies

C++ Type:std::vector

Options:

Description:The list of boundary IDs from the mesh where this boundary condition applies

• blockThe list of block ids (SubdomainID) that this object will be applied

C++ Type:std::vector

Options:

Description:The list of block ids (SubdomainID) that this object will be applied

### Optional Parameters

• output_propertiesList of material properties, from this material, to output (outputs must also be defined to an output type)

C++ Type:std::vector

Options:

Description:List of material properties, from this material, to output (outputs must also be defined to an output type)

• outputsnone Vector of output names were you would like to restrict the output of variables(s) associated with this object

Default:none

C++ Type:std::vector

Options:

Description:Vector of output names were you would like to restrict the output of variables(s) associated with this object

### Outputs Parameters

• enableTrueSet the enabled status of the MooseObject.

Default:True

C++ Type:bool

Options:

Description:Set the enabled status of the MooseObject.

• use_displaced_meshFalseWhether or not this object should use the displaced mesh for computation. Note that in the case this is true but no displacements are provided in the Mesh block the undisplaced mesh will still be used.

Default:False

C++ Type:bool

Options:

Description:Whether or not this object should use the displaced mesh for computation. Note that in the case this is true but no displacements are provided in the Mesh block the undisplaced mesh will still be used.

• control_tagsAdds user-defined labels for accessing object parameters via control logic.

C++ Type:std::vector

Options:

Description:Adds user-defined labels for accessing object parameters via control logic.

• seed0The seed for the master random number generator

Default:0

C++ Type:unsigned int

Options:

Description:The seed for the master random number generator

• implicitTrueDetermines whether this object is calculated using an implicit or explicit form

Default:True

C++ Type:bool

Options:

Description:Determines whether this object is calculated using an implicit or explicit form

• constant_onNONEWhen ELEMENT, MOOSE will only call computeQpProperties() for the 0th quadrature point, and then copy that value to the other qps.When SUBDOMAIN, MOOSE will only call computeSubdomainProperties() for the 0th quadrature point, and then copy that value to the other qps. Evaluations on element qps will be skipped

Default:NONE

C++ Type:MooseEnum

Options:NONE ELEMENT SUBDOMAIN

Description:When ELEMENT, MOOSE will only call computeQpProperties() for the 0th quadrature point, and then copy that value to the other qps.When SUBDOMAIN, MOOSE will only call computeSubdomainProperties() for the 0th quadrature point, and then copy that value to the other qps. Evaluations on element qps will be skipped


text:
Lemma 7.5.4. The functor $u_ p$ is a left adjoint to the functor $u^ p$. In other words the formula

$\mathop{Mor}\nolimits _{\textit{PSh}(\mathcal{C})}(\mathcal{F}, u^ p\mathcal{G}) = \mathop{Mor}\nolimits _{\textit{PSh}(\mathcal{D})}(u_ p\mathcal{F}, \mathcal{G})$

holds bifunctorially in $\mathcal{F}$ and $\mathcal{G}$.

Proof. Let $\mathcal{G}$ be a presheaf on $\mathcal{D}$ and let $\mathcal{F}$ be a presheaf on $\mathcal{C}$. We will show that the displayed formula holds by constructing maps either way. We will leave it to the reader to verify they are each others inverse.

Given a map $\alpha : u_ p \mathcal{F} \to \mathcal{G}$ we get $u^ p\alpha : u^ p u_ p \mathcal{F} \to u^ p \mathcal{G}$. Lemma 7.5.3 says that there is a map $\mathcal{F} \to u^ p u_ p \mathcal{F}$. The composition of the two gives the desired map. (The good thing about this construction is that it is clearly functorial in everything in sight.)

Conversely, given a map $\beta : \mathcal{F} \to u^ p\mathcal{G}$ we get a map $u_ p\beta : u_ p\mathcal{F} \to u_ p u^ p\mathcal{G}$. We claim that the functor $u^ p\mathcal{G}_ Y$ on $\mathcal{I}_ Y$ has a canonical map to the constant functor with value $\mathcal{G}(Y)$. Namely, for every object $(X, \phi )$ of $\mathcal{I}_ Y$, the value of $u^ p\mathcal{G}_ Y$ on this object is $\mathcal{G}(u(X))$ which maps to $\mathcal{G}(Y)$ by $\mathcal{G}(\phi ) = \phi ^*$. This is a transformation of functors because $\mathcal{G}$ is a functor itself. This leads to a map $u_ p u^ p \mathcal{G}(Y) \to \mathcal{G}(Y)$. Another trivial verification shows that this is functorial in $Y$ leading to a map of presheaves $u_ p u^ p \mathcal{G} \to \mathcal{G}$. The composition $u_ p\mathcal{F} \to u_ p u^ p\mathcal{G} \to \mathcal{G}$ is the desired map. $\square$

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:
Did you know there’s a small set of basic data structures and algorithms that underpin just about every software system that stores and retrieves data on disk, from databases to file systems and more?

There’s a fairly straightforward line of reasoning that you can follow to get more or less to today’s state of the art — all you need is some basic familiarity with data structures like hash tables and binary trees. That lines of reasoning goes something like this:

## Let’s Design a Store

We’ll start with one of the most basic kinds of storage systems: a key/value store, where we store both the keys and values on disk with the following interface:

• The client (our user) defines the structure of a key and a value
• Our write method adds a key/value pair to add to our store
• Our read method accepts a key, and reads the corresponding value from the store

This interface should seem familiar: it’s the basic key/value map interface provided by many programming languages and runtimes. If this seems like an odd interface to use for disk storage, keep in mind that most “real” storage systems rely on something that looks an awful lot like a key/value mapping, even if these systems don’t specifically use the words key and value. For example:

• Want to open a web page? You need to provide its URL (a key)
• Want to read a file? You need to provide its path (a key)
• Want to load a value from memory? You need to provide its address (a key)
• Want to query a database? You need to provide a primary key

Later on we’ll see how to gussy up an on-disk key/value store like this one to make it the core of a database, a file system, or maybe something else. But for now let’s focus on how to build a store like this one efficiently.

## The Key Problem

When designing something, a good question to answer first is: what’s the hard part? What should we spend most of our time thinking about how to solve?

Ironically, the ‘storing the data’ part of implementing a data store isn’t all too challenging. The hardware does all the work, so from a software perspective all we really need to do is set up the transfer and get out of the way.

The hard part is on the other end: retrieval. You have a disk (maybe a lot of disks) full of data, maybe written incrementally by lots of users over a long time. Today, a user comes along and requests a specific handful of bytes rattling around somewhere in there. How do you efficiently find the specific data the client requested?

In other words, storage is a search problem! (Also, the title of this section is a bad pun!)

So in designing our key/value store, the main challenge to overcome is designing an efficient on-disk key/value map data structure, where the write method efficiently sets up for reads to also be efficient.

## Map Data Strutures

Now that we know the goal, let’s start looking at our options. We want a key/value mapping data structure to store our data on disk — what are some map data structures we already know?

### Hash Tables

Hash tables (also known as hash maps or dictionaries) are easily the most popular data stuctures for mapping keys to values. Because they generally provide $O(1)$ insert and lookup, most developers reach for hash tables instinctively whenever they need a map.

The basic observation behind hash tables is that our computers already come pre-equipped with a map data structure implemented in hardware: namely memory, which most programming languages expose as arrays.

The main difference between an array and a general-purpose map is the ‘key’ type — arrays only accept integers between 0 and array_size - 1 as keys, whereas general purpose maps accept any type. Hash tables reconcile this using a hash function, which is a function that takes an instance of a key (of any type) and maps it to a unique array index mathematically:

int hash<T>(T key) { ... }

Assuming the hash() function can assign each key a unique array index, then all we need to do is map the key to an array index and get/put items by modifying the array item at that index, roughly like this:

/* put: */ thearray[hash(key)] = value;
/* get: */ return thearray[hash(key)];

In real life, there are only a few cases where it’s possible to uniquely map every key to an array index; usually there are more possible keys than there are slots in the array, for example. Cases where different keys map to the same array index are called hash collisions.

Much work has been done to design hash tables that handle collisions gracefully, as well as in designing hash functions that resist causing collisions in the first place. But the fact remains that collisions are a fact of life, and no collision-handling strategy does better than $O(\log N)$. Even so, you can think of hash tables as having $O(1)$ insert and lookup as long as you don’t have a lot of collisions, and you can generally achieve a low collision rate without much tuning as long as your data set is relatively small.

### Binary Search Trees

Although they’re less common, binary search trees are another valid way to represent a key/value mapping.

The basic idea is to construct a tree, where each node has a key/value pair as well as pointers to two child nodes. These nodes are sorted: given a node, all nodes that can be reached from the current node’s left child pointer have keys that are ‘less’ than the current node’s key, and all nodes reachable from the right child have keys ‘greater’ than the current node’s key:

Diagram

This tree might not look so sorted if you read it top to bottom, but it clearly is if you start from the left and go right, allowing your eyes to jump up and down the different levels as needed (try it!).

It can be shown that, with this data structure, it takes $O(\log{N})$ time to insert a key/value pair or to find a node with a given key. Even if this isn’t technically constant time, the $\log$ function grows very slowly, and many datasets are small enough that the difference is barely discernable. Plus, for binary search trees, $O(\log N)$ is truly the worst case: we don’t need to worry about tuning to keep the collision rate low.

## Maps on Disks

The logical next question is: can we use these to implement our key/value store? Are these data structures good choices?

You certainly can use hash tables or binary trees as the data structure for an on-disk key/value store: at the lowest level, disks expose an array of bytes just like memory does, so anything you can store in memory you can ultimately store on a disk in the exact same way. The only major difference between memory and disk interfaces is that memory gets wiped when the system powers off, whereas data on a disk is persistent across power cycles (that is, your computer turning off and on again).

So we can build a hash table or a binary tree on disk; but should we? People sometimes do, but it isn’t so common. That’s because, despite their similar interfaces, disks and memory have very different performance!

### Disk Performance

The different parts of your computer don’t run at the same speed. The following table gives a rough idea of just how much slower your disk is than the rest of your computer:

Device Latency (Actual) Latency (Human Scale)
CPU 0.4 ns 1 sec
Memory 100 ns 4 min
Disk (SSD) 50-150 μs 1.5-4 days
Disk (Rotational) 1-10 ms 1-9 months
Network Request 65-141 ms 5-11 years
(Thanks to Prowess for this visualization)

As you can see, readng and writing data on a disk is one of the slower things your code can do: even with a fast SSD, accesing the same data in memory is hundreds of times faster!

This leads us to our first idea we have already: can we try to keep data in memory instead of on disk? This is tried and true technique called caching.

### Caching

Here’s the basic idea again: we need to store our map on disk, because disks persist data across power cycles. However, we’d like to serve map queries from memory, because accessing memory is much faster than accessing disk. How can we do that?

If the data set is pretty small, the simple answer is to keep a full copy of the data in memory. Basically, all write operations first write on disk, then write to the copy of the map in memory; reads only need to query the copy in memory. This works as long as the data set is small, but disks are much larger than memory. What if the data set is too large to (reasonably) fit in memory?

The answer is simply that we can only keep part of the map in memory; if a caller happens to request a key that’s already cached in memory, then we can serve the request by querying the in-memory cached copy of the map; otherwise we take a performance hit and query the full map directly from disk.

How do we know which parts to keep in memory? To do a perfect job would require predicting the future, which is generally impossible to do perfectly without a time machine. Most caches for storage systems instead take advantage of two common observations about how users use storage systems:

• Spatial locality: clients are likely to query key ranges nearby key ranges they previously queried
• Temporal locality: clients are likely to revisit key ranges they recently queried

Putting these together and dropping the academic-speak, the basic suggestion is: when a client reads a key from the mapping, store a copy of that key/value pair as well as nearby key/value pairs in memory, in case the client comes back for the same key or a nearby key soon.

### Transfer Times and I/O Sizes

Okay, so we know we want to cache our map to make at least some, hopefully a lot of queries faster by serving from memory. What else can we do to maximize performance?

Here’s an interesting observation about the disk hardware performance: Take a look at these results from a little test I ran on my computer’s main disk (an SSD):

For this test, I executed many reads and writes from my disk using different I/O sizes (the number of bytes transferred per request). In the graphs above, the horizontal axis shows this I/O size, and the vertical axis shows the average latency (time to execute the transfer) for each I/O size in milliseconds.

Conventional wisdom says the time it takes to read or write data is proportional to how much data you want to read or write; if this were true, we would expect to see the latency grow exponentially in these graphs, because the horizontal axis grows exponentially (it doubles at each point) …

.. and that is eventually what happens, but the left side of each graph is roughly flat. This means, on average, the time it took to transfer 1 KB of data is about the same as it took to transfer 32 KB of data. (How could that be? This happens because there’s a fixed cost of setting up a disk I/O operation, which dominates the cost of actually reading/writing data unless you’re trying to read or write a lot of data.)

The conclusion, then, is that it’s okay to read a few kilobytes of extra data any time we only need a handful of bytes from disk. (If you think about it, this ought to play nicely with the caching strategies we mentioned above, eh?)

### Access Counts (Constants Matter!)

Let’s take another look at the latency table from earlier, but this time let’s use the latencies to figure out how many ‘things’ we can do with each device per second:

Device Latency (Actual) Operations / Second
CPU 0.4 ns 2,500,000,000
Memory 100 ns 10,000,000
Disk (SSD) 50-150 μs 6,700-20,000
Disk (Rotational) 1-10 ms 100-1,000
Network Request 65-141 ms 7-16

(All I did here was invert each latency — for example, there are 2.5 billion 0.4-ns intervals per second.)

The key thing to notice is that disks don’t give you all too many operations per second to work with, especially at the lower end (slower SSDs / rotational disks). Even if our map data structure has good big-$O$ performance, the absolute number of disk reads/writes is also important — if every client request causes us to do a few dozen disk operations, we’ll exhaust the disk’s throughput pretty quickly.

## Evaluating our Data Structures

Putting together everything we just learned about disk hardware performance, here’s how we can summarize the design criteria that we want to design our map data structure around:

Say we’re storing small key/value pairs (say, around 100 bytes each).

Our map data structure should minimize the number of individual disk accesses

… even if that means each operation transfers more data than strictly needed (up to a limit).

And, we plan to cache portions of this data structure in memory to exploit spatial and temporal locality in the client’s workload

So, how do hash tables and binary trees stack up?

### Hash Tables

TODO scrambling the keys destroys any inherent spatial locality in the data structure. But we can’t not scramble the keys, or we’ll get more frequent collisions and worse performance

TODO and on top of that, there’s also no bound to how many disk accesses a single query might require. Sure it’s usually just one disk read, which is great, but worst case collision handling can lead to lots of disk accesses.

TODO so we don’t really like these

### Binary Trees

TODO now this feels like a step in the right direction: at least the data structure is sorted right? Wrong! The links between nodes might provide us with a logical sort order, but on disk the nodes are scrambled around anyways. (Diagram showing the same scrambling pattern as the hash table, except now there’s a sentinel value labeled ‘root of tree’ and we add a bunch of inter-node arrows linking everything up. Showcase this side by side with the same ‘logical’ tree diagram as before.)

TODO these also have a real problem in terms of access counts! Consider a tree with 1 million elements: $\log_2(1,000,000) \approx 20$ disk accesses per read, which on a rotational disk means $20 \times 10 ms = 200$ ms per read. That means a single disk serving a binary tree-based index could only serve a whopping 5 requests per second — talk about cost-inefficient!

### What Did We Learn?

TODO we want a sorted data structure, so that there’s inherent spatial locality in the map itself

TODO we want the items in this data structure to be sorted even on disk, so we can ‘over read’ and cache the results

TODO and finally, we want to minimize the number of disk accesses needed to read an item

TODO and it turns out there’s a data structure that does a fairly good job at all of these …

## B-Trees

TODO

Okay, so we did a better job motivating how we’re going to get from binary trees to b-trees, which means now we can start to spell it out.

Basically, what I want to say is, start by noticing you can binary search a binary search tree by traversing it, but you can also binary search an array. What if our key value map was a gigantic array?

Problem: Updates might require rewriting all data on the disk, holy cow that’s slow

Oh yeah, that binary tree structure was helping us on insert

Okay, here’s the size observation: writing a ~4-16K batch of items is about as fast as writing a single item. Reading a 4-16K batch of items is about as fast as reading a single item. So what if we ‘smooshed’ the binary tree down into 4-16K runs of sorted items? (Diagram.)

And that’s precisely the core idea behind a b-tree!

Intuitively, the basic idea of a b-tree is to start with a binary search tree and ‘smoosh’ it down, kind of like this:

Diagram

Another way to think of this is making a binary tree ‘wider’ — whereas a binary tree has two children per node, a b-tree is an ‘$N$-ary’ tree with $N$ children per node (where $N$ is often in the hundreds). Typically, we pick a b-tree node size between 8 and 64 kilobytes, and stuff in as many key/value/child pairs as will fit.

To search a b-tree, we first read the root node from disk. We then search that node’s items array looking for either the item we want, or a gap between two items where our item would appear. In the latter case, we follow the child pointer to another node, which we then read from disk and search in the same way, recursively:

Diagram

We’re fundamentally still binary-searching a sorted collection as a tree, so the search complexity of our map is still $O(\log N$). However, since there are hundreds of items per node, there are hundreds times fewer nodes in a b-tree than there would be in a binary search tree with the same items. This saves us a lot of disk reads during searches.

Constructing a b-tree is a little more involved, but nothing we can’t handle. Wikipedia has a pretty good writeup if you’re curious about learning more.

### Nice Properties of B-Trees

Compared to binary search trees, what nice properties do we get by ‘smooshing’ the tree down into a wider, shallower structure with large nodes?

The main advantage is making it almost trivial to build an in-memory cache that exploits both spatial and temporal locality. All we need to do is cache a copy of each b-tree node we’ve accessed recently: if the client comes queries a nearby key soon, chances are very good that key is in the b-tree node we just cached, so we can serve the query from the cached node with no disk reads.

Even better, reading a b-tree’s large nodes is ‘free’ compared to reading a binary search tree’s very small nodes, because the time it takes to read a handful of bytes from a disk is the same as it takes to read a handful of kilobytes — remember these graphs?

Finally, even if we don’t have the requested data in our cache, the very high branching factor of a b-tree keeps it shallow; for example, if you had a million items in a b-tree with 256 items per node, your tree would only have three levels, which means even if your cache were empty, you would only need to execute 3 disk reads to serve a client query (compared to 20 for binary trees, as we estimated earlier).

In practice, though, you’d basically never execute all three of those disk reads, because there’s an extremely good chance you cached some of the internal nodes already. For example, as long as you’ve queried any part of the tree recently, you already have the root node cached; that’s one less disk read you need.

### The Ubiquitous B-Tree

For disk query performance, it’s hard to beat a b-tree, which is why they’re used across all sorts of data stores, from file systems to databases to caches and more. Much work has gone into optimizing b-trees, and there are many variants (the Wikipedia article on b-trees includes a nice overview of the different variants people have come up with).

But, for now, let’s get back to our key/value store.

## Let’s Build a Key-Value Store

Now that we have a good data structure in mind, let’s build a key/value store on disk using a b-tree, and analyze its performance.

Complete the key-value store interface on top of this tree. Should be very easy.

## Let’s Build a Database

This was originally written before we refactored the post to describe a generic ‘key/value store’ first, so this section may need some redrafting.

Overview showing what a database table looks like, with a diagram

We can decompose a row into a key-value mapping by examininng the table schema

Diagram

A table, then, is a sorted array of this key-value mapping.

So then the obvious approach is to store the database as a b-tree of rows.

Diagram showing the example table on one side, the same rows in a b-tree on the other side

Each record is a row, which can be decomposed into both a key and a value as described above.

Let’s look at how common queries work

• Insert - show how this is a row insert
• Select - with a single key
• Select - with a range of keys
• Delete -

To complete your database now all you need is a transaction manager (which locks ranges of keys that are being operated on, to provide isolation) and a query parser (giving users an interface to your database)

Huzzah! We solved storage systems … or did we? How do you handle data that’s larger than what can fit in a single b-tree node?

This is the purview of a different, but closely related kind of storage system . . .

## File Systems

Databases vs file systems: similar in principle, differ in target workloads. Databases optimize for large numbers of relatively small ‘records’ (rows), whereas file systems optimize for smaller numbers of relatively larger ‘files.’ Plenty of overlap.

Although file systems are not tied to b-trees as closely as databases usually are, many modern file systems use b-trees ubiquitously (such as btrfs on Linux, ReFS on Windows?, AFS on macOS? Others worth mentinoinng?)

### Naming Hierarchy

Very quick overview of files and directories. Show how this is basically the database problem all over again, and how b-trees are a good fit

## File Contents and Handling Large Items

The database design assumed many small key and value records, but files can get pretty darn big: the name is still a small key, but the value (file contents) can be gigabytes to terabytes in size. You can’t stick these file contents in your b-tree because they’re often much larger than any particular node of your b-tree.

Do we need to throw away our system and start over with something new? How does a file system handle these large items?

Think about the interface a disk provides, and fundamentally how a b-tree is laid out on disk

Diagram showing a byte array, b-tree nodes in that byte array pointing to each other

Idea: drop data anywhere on disk you have room to put it, then use a b-tree record to point to the data by its disk address:

Diagram

### Disk Allocation

Explore the problem of allocating space on a disk, both for allocating blocks of space for file contents and for allocating blocks of space for b-tree nodes. Note that a b-tree can even be used for this.

Mention fragmentation, this is more than just a data structures problem, very similar to writing a memory allocator since disks are very similar to memory

## When to Build Storage Systems

Salvage some of the content from the old ‘optimizing and tradeoffs’ section. The main argument is that every system optimizes for certain workloads and the expense of being worse at other workloads, and sometimes you have a workload that nobody has ever optimized for — and that’s when you break out this theory and go build your own system.

## Where To Next

Other concerns like resiliency (checksums), concurrency control

New unconventional types of storage devices which meld performance aspects of disks and memory

Append-only stores and the unique challenges they pose

Distributed stores and the unique challenges they pose


text:
# software for symbolic math plotter

I'm wondering if there is a plotting tool out there that will work in symbolic math?

For example, if I plot $x+y=a$ and $y=x$ on a chart, I should be able to click on the point of intersection to get $\left(\large \frac{a}{2},\frac{a}{2}\right)$.

-
How do you expect it to plot $x + y = a$ without knowing the value of $a$ (e.g. whether it's positive or negative, which affects where the line should be drawn)? –  ShreevatsaR Jun 16 '11 at 20:52
BTW, not exactly what you want, but Geogebra is great. You can give it a specific value of $a$ like $a=5$ or something, ask it to plot the lines $x+y=a$ and $y=x$, ask it to compute their intersection, and it will will show you the coordinates and automatically update them as you modify $a$. –  ShreevatsaR Jun 16 '11 at 20:54
I suppose Mathematica (or WolframAlpha) will do that, but that might be a bit heavier than what you need. –  Jack Henahan Jun 16 '11 at 21:30
@ShreevatsaR: Do you know whether you can save your "Geogebra-ic" work an image file (.jpg, .png, .gif), etc., or is it only "save-able" as a Geogebra file that only Geogebra can open? Just curious. –  amWhy Jun 16 '11 at 21:48
@amWhy: Geogebra can export files in .png, .bmp, and .eps, as far as I can remember. –  Beni Bogosel Jun 17 '11 at 0:08
show 1 more comment

Another soft for geometric drawings, which is maybe better than Geometer's Sketchpad, and (more important) free is Geogebra. In Geogebra you can plot lines given by certain equations (unfortunately, I don't think symbolic equations work), and you have a left panel with all the objects you have drawn and also their equations. There is a tool for intersection of two objects, and a new point is created. Every point can be found in the left panel with its coordinates.

A program which does symbolic computation and symbolic plotting at a very advanced level is Maple. Unfortunately, this is not free.

To do symbolic plotting is impossible on computer, since all the data on the screen needs coordinates to look the way it is. The best compromise, which I think is available with Geogebra, is to introduce a parameter, which varies between some fixed values, and can be modified with a cursor. Maple has this function for sure; I know that I've used it a couple of times.

-
Symbolic equations sort of work, i.e., they work if all the symbols have previously been given values. :-) (As you said in your last paragraph. E.g. you can give it a=0, b=0, r=1, and ask Geogebra to plot $(x-a)^2 + (y-b)^2 = r^2$, and changing the values of a, b, r will change the circle. This is about as much as you can expect a computer to do, as far as I can imagine.) –  ShreevatsaR Jun 17 '11 at 7:58
There's a student version for $29.95, and I believe a free trial version. The resources are fabulous (tutorials, exchange forums, downloadable/accessible sketches created by others, lessons, etc.) and it is really quite user friendly. It may even be "usable" on-line (free). Not sure on that. I believe it also allows you to create java applets on web pages, but it's usually what I turn to for plotting, geometric constructions, determining points of intersection, area, etc. Your "sketches" can be saved, reloaded to edit, saved as image files, etc. If you have an iPhone (and iPod touch) or an iPad, there's a program ($30?) called Spacetime that you can purchase to download and use on your device (making it essentially a graphing calculator). You're better off with the Wolfram App mentioned below if you're interested in access to mobile graphing and much more.
By the way, for the iPhone (and iPod touch) and iPad, there's an app (almost free, $1.99 USD - one time payment) available for downloading mobile access to Wolfram Alpha to your i-Pad-Pod-phone. - Can Geometer's Sketchpad plot$x+y=a$without knowing what$a$is (as the OP seems to want)? – ShreevatsaR Jun 17 '11 at 7:55 @ShreevatsaR: pretty much as you describe it for geogebra in your comment to another answer: it allows you to vary the value of a variable, which changes the corresponding function/graph, etc. – amWhy Jun 17 '11 at 19:22 @amWhy: Nice suggestions +1 – Amzoti May 7 '13 at 2:25 +111111111111111 – B. S. Jul 9 '13 at 6:31 add comment Another way is to use Maple 15, 16 or recently version 17. In this powerful software which is famous in symbolic computations, you can easily probe the point of intersection as well as other useful points in any certain plots. I could do that for you while$a=4\$:


text:
## Parsing GPS data with Bash

May 7, 2013

Last time we looked at how to get the data to the GPS and now we will have a look at how to parse the data. Turns out that except for the check-sum, everything is pretty straight forward, even in Bash.

So, why bash in the first place? Well, there’s not real reason except that for the something else I’m working on, it’s the ideal glue-code language, allowing me to invoke simply other programs that I do not want to re-code (or take parts of) to do what I want. I must say that I even have a C# version of the GPS data grabber, but while fancier, it does not bring much more than the Bash version.

## Reading GPS data with Bash

April 30, 2013

I am presently working on something that requires geolocation. Not knowing much about GPSes and related topics, I decided to get a USB GPS. This week, let’s have a look at how we can extract information from the USB GPS using Bash.

The first step is to locate your USB GPS as a device. If it’s NMEA compliant, it should mount automagically as a USB serial port. You would think that lsusb -v would show you the device, but it does not always. Sometimes it shows as “Brand X GPS”, sometimes it only shows as a generic device, say “MediaTek Inc.”, or even as a modem. It will typically show up as /dev/ttyUSB0 or /dev/ttyACM0.

## Shallow Constitude

March 19, 2013

In programming languages, there are constructs that are of little pragmatic importance (that is, they do not really affect how code behaves or what code is generated by the compiler) but are of great “social” importance as they instruct the programmer as to what contract the code complies to.

One of those constructs in C++ is the const (and other access modifiers) that explicitly states to the programmer that this function argument will be treated as read-only, and that it’s safe to pass your data to it, it won’t be modified. But is it all but security theater?

## Compressed Series (Part I)

March 5, 2013

Numerical methods are generally rather hard to get right because of error propagation due to the limited precision of floats (or even doubles). This seems to be especially true with methods involving series, where a usually large number of ever diminishing terms must added to attain something that looks like convergence. Even fairly simple sequences such as

$\displaystyle e=\sum_{n=0}^\infty \frac{1}{n!}$

may be complex to evaluate. First, $n!$ is cumbersome, and $\displaystyle \frac{1}{n!}$ becomes small exceedingly rapidly.

## Float16

February 12, 2013

The possible strategies for data compression fall into two main categories: lossless and lossy compression. Lossless compression means that you retrieve exactly what went in after compression, while lossy means that some information was destroyed to get better compression, meaning that you do not retrieve the original data, but only a reasonable reconstruction (for various definitions of “reasonable”).

Destroying information is usually performed using transforms and quantization. Transforms map the original data onto a space were the unimportant variations are easily identified, and on which quantization can be applied without affecting the original signal too much. For quantization, the first approach is to simply reduce precision, somehow “rounding” the values onto a smaller set of admissible values. For decimal numbers, this operation is rounding (or truncating) to the $n$th digit (with $n$ smaller than the original precision). A much better approach is to minimize an explicit error function, choosing the smaller set of values in a way that minimizes the expected error (or maximum error, depending on how you formulate your problem).

## An (Incomplete) Experiment with Sensors

January 29, 2013

When you have lm-sensors installed on Linux, you can invoke sensors to list all detected sensors and their states. While it is generally of mild interest except when you suspect that something’s wrong with your box—or, more precisely, when you want to make sure something doesn’t go wrong.

Amongst the sensors, there are temperature sensors that gives you information about the chipset and CPU. You can also find out about fan speeds. So I wondered if could use the sensors to see if there’s a significant difference between when the computer is idle and when I am using it. I thought I could, maybe, also see temperature differences between day and night.

## Fat, Slim Pointers

July 31, 2012

64 bits address space lets us access tons more memory than 32 bits, but with a catch: the pointers themselves are … well, yes, 64 bits. 8 bytes. Which eventually pile up to make a whole lot of memory devoted to pointers if you use pointer-rich data structures. Can we do something about this?

Well, in ye goode olde dayes of 16 bits/32 bits computing, we had some compilers that could deal with near and far pointers; the near, 16-bit pointers being relative to one of the segments, possibly the stack segment, and the far, 32-bits pointers being absolute or relative to a segment. This, of course, made programming pointlessly complicated as each pointer was to be used in its correct context to point to the right thing.

## Artsy Recycling

June 19, 2012

Even when you actually want to recycle computer parts (especially scrap parts that do not quite work anymore) it’s quite hard to do so. One possible solution is to simply chuck everything in the usual recycling bin and hope for the best. Or you can try to find a metal reseller. Or you can use the parts in a creative way. Kind of.

I disassembled the CFM01 and got quite a lot of spare parts from the 1U Pentium III servers. The casings aren’t all that interesting since they’re fairly cheap (compared to, say, a Dell PowerEdge server) and the CPUs are useless. Nobody wants them. Even recycling the all-copper heat sink proved a problem. So I used them differently.

## New Way of Computing Square Roots?

April 17, 2012

I sometimes have quite nerdy readings. As of late, I’ve been reading Le fabuleux destin de $\sqrt{2}$ (The Fabulous Destiny of $\sqrt{2}$, one might translate) by Benoît Rittaud. This book is a treasure trove of $\sqrt{2}$ facts, and one caught my eye more than the others so far: an iterative method to compute square roots of any (positive) number.

When the method is first presented, he leaves to the reader to find a demonstration (though he gives one much later on, several chapters later), but let’s see what we can find.

## UEID (Unique Enough IDs, part 2)

March 13, 2012

As part of an open-source project I’m working on (right now, we are still at the technical feasibility stage where we explore and eliminate technical risks, full disclosure will come later) we have to issue session numbers. They’re not session numbers in the usual sense, but they still need to be unique, and not amenable to simple attacks.

There are a couple of ways of generating unique session numbers. RFC 4122-compliant unique IDs is one possible way.