text:
GMAT Question of the Day - Daily to your Mailbox; hard ones only

 It is currently 21 Sep 2018, 14:43

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?

Author Message
TAGS:

### Hide Tags

Math Expert
Joined: 02 Sep 2009
Posts: 49300
If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?  [#permalink]

### Show Tags

12 Oct 2017, 03:40
00:00

Difficulty:

15% (low)

Question Stats:

74% (00:54) correct 26% (01:01) wrong based on 53 sessions

### HideShow timer Statistics

If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?

A. 1 : 3
B. 3 : 1
C. 3 : 4
D. 1 : 1
E. 4 : 3

_________________
Math Expert
Joined: 02 Sep 2009
Posts: 49300
Re: If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?  [#permalink]

### Show Tags

12 Oct 2017, 03:46
Bunuel wrote:
If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?

A. 1 : 3
B. 3 : 1
C. 3 : 4
D. 1 : 1
E. 4 : 3

$$\frac{1}{2}*b = c$$, thus $$b = 2c$$;
$$a = 2b = 4c$$.
$$4c = 3d$$, thus $$d = \frac{4c}{3}$$.

$$\frac{d}{a}=\frac{\frac{4c}{3}}{4c}=\frac{4c}{3}*\frac{1}{4c}=\frac{1}{3}$$.

_________________
SVP
Joined: 26 Mar 2013
Posts: 1808
Re: If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?  [#permalink]

### Show Tags

12 Oct 2017, 04:06
Bunuel wrote:
If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?

A. 1 : 3
B. 3 : 1
C. 3 : 4
D. 1 : 1
E. 4 : 3

Let b=6.......then a =12, c=3, d=4

$$\frac{d}{a} =\frac{4}{12}= \frac{1}{3}$$

Senior SC Moderator
Joined: 22 May 2016
Posts: 1978
If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?  [#permalink]

### Show Tags

12 Oct 2017, 09:21
Bunuel wrote:
If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?

A. 1 : 3
B. 3 : 1
C. 3 : 4
D. 1 : 1
E. 4 : 3

a is the greatest of three:
a = 2b, b = 2c, so a > c

d's relation to a is not evident in an instant, so I picked a larger multiple of the coefficients 2, 3, and 4

Let a = 36
a = 2b
36 = 2b
b = 18

1/2 * b = c
b = 2c
18 = 2c
c = 9

4c = 3d
36 = 3d
d = 12

Ratio of d to a

$$\frac{12}{36} =\frac{1}{3} = (1:3)$$

_________________

In the depths of winter, I finally learned
that within me there lay an invincible summer.

Target Test Prep Representative
Affiliations: Target Test Prep
Joined: 04 Mar 2011
Posts: 2835
Re: If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?  [#permalink]

### Show Tags

16 Oct 2017, 16:47
Bunuel wrote:
If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a?

A. 1 : 3
B. 3 : 1
C. 3 : 4
D. 1 : 1
E. 4 : 3

We can multiply the equation 1/2*b = c by 4 and we have:

2b = 4c

Since a = 2b:

a = 4c

Since 4c = 3d:

3d = a

So, d/a = 1/3

_________________

Jeffery Miller

GMAT Quant Self-Study Course
500+ lessons 3000+ practice problems 800+ HD solutions

Re: If a = 2b, 1/2*b = c, and 4c = 3d, then what is the ratio of d to a? &nbs [#permalink] 16 Oct 2017, 16:47
Display posts from previous: Sort by

# Events & Promotions

 Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.


text:
Question

# The system of equations |z−3|=√2 and z (1 + i)+ ¯z (1−i)=6 has

A
no solution
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
infinitely many solutions
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
only two solutions
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
D
Only one solution
No worries! We‘ve got your back. Try BYJU‘S free classes today!
Open in App
Solution

## The correct option is B only two solutionsPutting z = x + iy in the given equations, we have (z+¯z)+i(z−¯z)=6i.e.x−y=3…… (1) and |z−3|=√2i.e.(x−3)2+y2=2…… (2) Solving equations (1) and (2), we have y = -1, 1 and corresponding x = 2, 4 Hence, there are only two solutions, viz. z = 2 - I, 4 + i

Suggest Corrections
0

format: plain


text:
# A solution of sodium hydroxide is standardized against potassium hydrogen phthalate. From the following data, calculate the molarity of NaOH solution? (See details below)

Mar 10, 2017

$M \left(N a O H\right) = 0 , 0688 \frac{m o l}{L}$
$V \left(N a O H\right) = 0 , 0469 L$

#### Explanation:

For a titration is necessary that the moles of NaOH are equivalent to the mole of KHP (that have a MM of 204,22g/mol).

$m o l K H P = \frac{0 , 436 g}{204 , 22 \left(\frac{g}{m o l}\right)} = 0 , 00213 m o l$.

V of NaOH used =(31,26-0,23) = 31,03 mL = 0,03103 L

$m o l N a O H = M V = M 0 , 03103 L$
but the mol of the two substance are the same therefore
Molarity of NaOH = (mol KHP)/ (V NaOH used for titration): $M \left(N a O H\right) = \frac{0 , 00213 m o l}{0 , 03103 L} = 0 , 0688 \frac{m o l}{L}$.
Since NaOH is monovalent its molarity is equal to its Normality =0,0688 (eq)/L.

For the oxalic acid (MM= 90,03 g/mol; ME = 45,01 g/eq) is necessary a double quantity of moles of NaOH, since oxalic acid is biprotic (1 eq = 2 mol), or (that is the same) the Equivalent Mass of the oxalic acid is the half of the Molecular Mass .
$e q {H}_{2} {C}_{2} {O}_{4} = \frac{0 , 1453 g}{45 , 01 \frac{g}{e q}} = 0 , 003228 e q$
$V \left(N a O H\right) = \frac{e q {H}_{2} {C}_{2} {O}_{4}}{N \left(N a O H\right)} = \frac{0 , 003228 e q}{0 , 0688 \frac{e q}{L}} = 0 , 0469 L = 46 , 9 m L$

Mar 11, 2017

$\left[N a O H \left(a q\right)\right] = 7.158 \times {10}^{-} 2 \cdot m o l \cdot {L}^{-} 1$

#### Explanation:

We need (i) a stoichiometrically balanced equation for our primary standard:

${C}_{6} {H}_{4} \left(C {O}_{2}^{-} {K}^{+}\right) \left(C {O}_{2} H\right) + N a O H \rightarrow {C}_{6} {H}_{4} \left(C {O}_{2}^{-} {K}^{+}\right) \left(C {O}_{2}^{-} N {a}^{+}\right) + {H}_{2} O$

And this is a convienient 1:1 stoichiometry, so moles of phthalate is equivalent to moles of base:

And (ii) equivalent quantities of $\text{KHP}$,

i.e. $\text{Moles of KHP} = \frac{0.4536 \cdot g}{204.22 \cdot g \cdot m o {l}^{-} 1} = 2.221 \times {10}^{-} 3 m o l$.

Given the stoichiometry, this molar quantity was contained in the volume of titrant, i.e.

$\left[N a O H \left(a q\right)\right] = \text{Moles of base"/"Volume of titrant}$

$\frac{\frac{0.4536 \cdot g}{204.22 \cdot g \cdot m o {l}^{-} 1}}{\left(31.26 - 0.23\right) \times {10}^{-} 3 L} = 7.158 \times {10}^{-} 2 \cdot m o l \cdot {L}^{-} 1$.

So we have $N a O H$, and we use to titrate a mass of oxalic acid. You must know this is a diacid, i.e. $H {O}_{2} C - C {O}_{2} H$, with a molecular mass of $90.03 \cdot g \cdot m o {l}^{-} 1$ (the dihydrate is much common, i.e. $H {O}_{2} C - C {O}_{2} H \cdot {\left(O {H}_{2}\right)}_{2}$, so if your results are off, question the quality of your oxalic acid, and you can assess this easily by melting point).

Again, we need a stoichiometric equation:

$\text{HO"_2"CCO"_2"H"(aq) + "2NaOH"(aq) rarr "Na"^(+)""^(-)"O"_2"CCO"_2^(-)"Na"^+ +2"H"_2"O} \left(l\right)$

$\text{Moles of oxalic acid}$ $=$ $\frac{0.1453 \cdot g}{90.03 \cdot g \cdot m o {l}^{-} 1} = 1.614 \times {10}^{-} 3 \cdot m o l$.

$\text{Volume of NaOH titrant required}$ $=$ (2xx1.614xx10^-3*mol)/(7.158xx10^-2*mol*L^-1)xx1000*mL*L^-1=??*mL.

And thus, we require under $50 \cdot m L$ of titrant, and this is a good volume for a titration.

This is a long problem, so I certainly would check the arithmetic. It is all too easy to make an error.


text:
## Chapter 23Solutions for seventh week’s assignments

Also available as PDF.

Note: These are my approaches to these problems. There are many ways to tackle each.

### 23.1 Problem set 4.1

Problem 2
The (non-repeated) factorizations are 1 ⋅ 35 and 5 ⋅ 7. Drawing those as boxes is straight-forward.
Problem 4
 Factors of 18 1 2 3 6 9 18 Quotient 18 9 6 3 2 1
Problem 7
• 48 = 1 ⋅ 48 = 2 ⋅ 24 = 3 ⋅ 16 = 4 ⋅ 6, so the factors are 1, 2, 3, 4, 6, 16, 24, and 48.
• 54 = 1 ⋅ 54 = 2 ⋅ 27 = 3 ⋅ 18 = 6 ⋅ 9, so the factors are 1, 2, 4, 6, 9 18, 27, 54.
• The largest common factor then is 6.
Problem 9
• 48 = {2}^{4} ⋅ {3}^{1}
• 108 = {2}^{2} ⋅ {3}^{3}
• 2250 = {2}^{2} ⋅ {3}^{2} ⋅ {5}^{3}
• 24\kern 1.66702pt 750 = {2}^{1} ⋅ {3}^{2} ⋅ {5}^{3} ⋅ 1{1}^{1}
Problem 10
• Yes, because all primes are shared and no powers of the primes exceed those of a.
• No, because {3}^{2} has a larger exponent than the {3}^{1} in a.
• a∕b = ({2}^{3} ⋅ {3}^{1} ⋅ {7}^{2})∕({2}^{2} ⋅ {3}^{1}) = {2}^{3-2} ⋅ {3}^{1-1} ⋅ {7}^{2-0} = {2}^{1} ⋅ {7}^{2}.
• There are (2 + 1) ⋅ (1 + 1) ⋅ (2 + 1) = 18 factors of a.
• We can make a list by running up the exponents:

 {2}^{0} ⋅ {3}^{0} ⋅ {7}^{0} {2}^{1} ⋅ {3}^{0} ⋅ {7}^{0} {2}^{2} ⋅ {3}^{0} ⋅ {7}^{0} {2}^{3} ⋅ {3}^{0} ⋅ {7}^{0} {2}^{0} ⋅ {3}^{1} ⋅ {7}^{0} {2}^{1} ⋅ {3}^{1} ⋅ {7}^{0} {2}^{2} ⋅ {3}^{1} ⋅ {7}^{0} {2}^{3} ⋅ {3}^{1} ⋅ {7}^{0} {2}^{0} ⋅ {3}^{0} ⋅ {7}^{1} {2}^{1} ⋅ {3}^{0} ⋅ {7}^{1} {2}^{2} ⋅ {3}^{0} ⋅ {7}^{1} {2}^{3} ⋅ {3}^{0} ⋅ {7}^{1} {2}^{0} ⋅ {3}^{1} ⋅ {7}^{1} {2}^{1} ⋅ {3}^{1} ⋅ {7}^{1} {2}^{2} ⋅ {3}^{1} ⋅ {7}^{1} {2}^{3} ⋅ {3}^{1} ⋅ {7}^{1} {2}^{0} ⋅ {3}^{0} ⋅ {7}^{2} {2}^{1} ⋅ {3}^{0} ⋅ {7}^{2} {2}^{2} ⋅ {3}^{0} ⋅ {7}^{2} {2}^{3} ⋅ {3}^{0} ⋅ {7}^{2} {2}^{0} ⋅ {3}^{1} ⋅ {7}^{2} {2}^{1} ⋅ {3}^{1} ⋅ {7}^{2} {2}^{2} ⋅ {3}^{1} ⋅ {7}^{2} {2}^{3} ⋅ {3}^{1} ⋅ {7}^{2}
Problem 13
No, it is only true that at least one prime factor cannot exceed \sqrt{n}. Consider 2 ⋅ 47 = 94, where both 2 and 47 are prime. We have \sqrt{94} < 10 but 47 > 10 > \sqrt{94}. But 2 < \sqrt{94}.
Problem 14
No. If n is not prime, some of its factors may split between b and c. For example, 2 ⋅ 3 = 6\mathrel{∣}18 = 2 ⋅ 9, but 6 ∤ 2 and 6 ∤ 9. The factors of n = 6, 2 and 3, are split between a = 2 and b = 9.
Problem 23
Here it is true. Consider the prime factorizations of b and c. If p\mathrel{∣}bc, then p must appear in one or both of those prime factorizations, and thus it must divide at least one of b and c.
Problem 24
Again, use the prime factorization of n. Because p and q are primes, they must appear in that factorization. Then pq\mathrel{∣}n because both appear, so you can commute products around to group (pq) and the rest of the factorization.

### 23.2 Two diagrams

8 ∤ 18:
18 = 2 ⋅ 8 + 2, so you can draw and count:
+
3 ∤ 11:
11 = 3 ⋅ 3 + 2:
+

### 23.3 Problem set 4.2

Problem 1
• 1554 is even, so divisible by 2, does not end in 5 or 0, so is not divisible by 5, and has digits that add to 0\kern 18mu ({\rm mod}\kern 6mu 3), so is divisible by 3.
• 1999 is not even, so is not divisible by 2, does not end in 5 or 0, so is not divisible by 5, and has digits that add to 1\kern 18mu ({\rm mod}\kern 6mu 3), so is not divisible by 3.
• 805 is not divisible by 2, is divisible by 5, and is not divisible by 3.
• 2450 is divisible by 2, is divisible by 5, and is not divisible by 3.
Problem 2
• 2 and 3
• 2 and 5
• 3 and 5
• 2, 3, and 5
Problem 8
The missing digit must be divisible by 2. Also, the sum of the digits must be congruent to 0 modulo 3. The non-blank digits already add to 0\kern 18mu ({\rm mod}\kern 6mu 3), so the missing digit must be a multiple of 3. There is only one even multiple of 3 less than 10, so the missing digit must be 6.
Problem 14
Expanding the positional notation and simplifying, abc,abc = a⋅(1{0}^{5}+1{0}^{2})+b⋅(1{0}^{4}+1{0}^{1})+c⋅(1{0}^{3}+1{0}^{0}) = (a⋅1{0}^{2}+b⋅1{0}^{1}+c)⋅(1{0}^{3}+1{0}^{0}) = abc⋅1001. Now 1001 = 7 ⋅ 11 ⋅ 13, so abc,abc is divisible by each of those.
Problem 15
• ab - ba = a ⋅ 10 + b - (b ⋅ 10 + a) = (a - b) ⋅ 10 + (b - a). Because 10 ≡ 1\kern 18mu ({\rm mod}\kern 6mu 9), this becomes a - b + b - a ≡ 0\kern 18mu ({\rm mod}\kern 6mu 9). The result always is a multiple of 9. Equivalently, we can rearrange (a - b) ⋅ 10 + (b - a) = (a - b) ⋅ 10 + -1 ⋅ (a - b) = (a - b) ⋅ (10 - 1) = 9(a - b), giving also which multiple of 9.
• Here the difference is (a - c) ⋅ 1{0}^{2} + 0 + (c - a) because the middle digit always cancels. Again, the result always is a multiple of 9 and we can rearrange (a-c)⋅1{0}^{2}+0+(c-a) = (a-c)⋅1{0}^{2}+-1⋅(a-c) = (a-c)⋅(1{0}^{2}-1) = 99(a-c) to see the result is a multiple of 99.

### 23.4 A familiar incomplete integer

Take a familiar incomplete integer, -679-. Using the expression of -679- as N = 1{0}^{4} ⋅ {x}_{4} + {x}_{0} + 6790, use 8\mathrel{∣}N to find {x}_{0}. Given that, use 9\mathrel{∣}N to find {x}_{4}. Now if 72 turkeys cost $-679-, what is the total? If 8\mathrel{∣}N then 8 divides the last three digits, so 8\mathrel{∣}790 + {x}_{0}. Thus 790 + {x}_{0} ≡ 0\kern 18mu ({\rm mod}\kern 6mu 8). Because 790 ≡ 6\kern 18mu ({\rm mod}\kern 6mu 8), we know that {x}_{0} ≡ 2\kern 18mu ({\rm mod}\kern 6mu 8). The only decimal digit satisfying {x}_{0} ≡ 2\kern 18mu ({\rm mod}\kern 6mu 8) is \mathbf{{x}_{0} = 2}. Now we have N = 1{0}^{4} ⋅ {x}_{4} + 6792. For 9\mathrel{∣}N, the sum of the digits must be zero modulo 9. Thus {x}_{4} + 6 + 7 + 9 + 2 ≡ 0\kern 18mu ({\rm mod}\kern 6mu 9), or {x}_{4} + 6 ≡ 0\kern 18mu ({\rm mod}\kern 6mu 9). Thus \mathbf{{x}_{4} = 3}, and \mathbf{N = 36792}. (I forgot the decimal place in the problem, so these are very expensive turkeys.) So if 72 turkeys cost$36792, each turkey costs $511. If I had remembered the decimal place correctly, the turkeys cost$5.11 each.


text:
# How do I find the value of sin 5pi / 6?

Then teach the underlying concepts
Don't copy without citing sources
preview
?

#### Explanation

Explain in detail...

#### Explanation:

I want someone to double check my answer

24
Dec 7, 2016

sin $\frac{5 \pi}{6}$= $\frac{1}{2}$

#### Explanation:

Sin $\frac{5 \pi}{6}$= sin $\left(\pi - \frac{\pi}{6}\right)$= sin $\frac{\pi}{6}$= sin 30 = $\frac{1}{2}$

Another way to think about it is to draw the angle in a Unit circle and create the "new" triangle in Quadrant II.

Drop a perpendicular to the x-axis and you will have the correct triangle to use.

From this triangle, you need the opposite leg length, which is $\frac{1}{2}$.
Since the hypotenuse is equal to 1 in the Unit circle, the opposite leg length is the answer for sine. (dividing by 1 is not necessary)

• 12 minutes ago
• 12 minutes ago
• 16 minutes ago
• 20 minutes ago
• 3 minutes ago
• 4 minutes ago
• 4 minutes ago
• 6 minutes ago
• 7 minutes ago
• 8 minutes ago
• 12 minutes ago
• 12 minutes ago
• 16 minutes ago
• 20 minutes ago


text:
# Velocity and Acceleration Question

1. Aug 31, 2008

### mossfan563

1. The problem statement, all variables and given/known data
The position of a particle moving along the x axis depends on the time according to the equation x = c(t^5) - b(t^7), where x is in meters and t in seconds. Let c and b have numerical values 2.6 m/s5 and 1.3 m/s7, respectively. From t = 0.0 s to t = 1.8 s, (a) what is the displacement of the particle? Find its velocity at times (b) 1.0 s, (c) 2.0 s, (d) 3.0 s, and (e) 4.0 s. Find its acceleration at (f) 1.0 s, (g) 2.0 s, (h) 3.0 s, and (i) 4.0 s.

2. The attempt at a solution
Do I try to take the derivative to try and get the velocity and acceleration answers?
And how do I find the displacement?

2. Aug 31, 2008

### LowlyPion

The displacement should be found by using the position function f(t) = x = c*t5 - b*t7 and then determining the difference between the two positions at the times given.

As to the rest of your question if velocity is $$\frac{dx}{dt}$$ and acceleration is $$\frac{dv}{dt}$$ then taking derivatives looks like a sound approach and then plug in the points asked for.


text:
# American Institute of Mathematical Sciences

January  2021, 26(1): 1-60. doi: 10.3934/dcdsb.2020231

## Bifurcations in periodic integrodifference equations in $C(\Omega)$ I: Analytical results and applications

 Institut für Mathematik, Universität Klagenfurt, Universitätsstraße 65–67, 9020 Klagenfurt, Austria

Received  January 2020 Revised  June 2020 Published  January 2021 Early access  July 2020

We study local bifurcations of periodic solutions to time-periodic (systems of) integrodifference equations over compact habitats. Such infinite-dimensional discrete dynamical systems arise in theoretical ecology as models to describe the spatial dispersal of species having nonoverlapping generations. Our explicit criteria allow us to identify branchings of fold- and crossing curve-type, which include the classical transcritical-, pitchfork- and flip-scenario as special cases. Indeed, not only tools to detect qualitative changes in models from e.g. spatial ecology and related simulations are provided, but these critical transitions are also classified. In addition, the bifurcation behavior of various time-periodic integrodifference equations is investigated and illustrated. This requires a combination of analytical methods and numerical tools based on Nyström discretization of the integral operators involved.

Citation: Christian Aarset, Christian Pötzsche. Bifurcations in periodic integrodifference equations in $C(\Omega)$ I: Analytical results and applications. Discrete and Continuous Dynamical Systems - B, 2021, 26 (1) : 1-60. doi: 10.3934/dcdsb.2020231
##### References:
 [1] C. Aarset and C. Pötzsche, Bifurcations in periodic integrodifference equations in $C(\Omega)$ II: Discrete torus bifurcations, Commun. Pure Appl. Anal., 19 (2020), 1847-1874. [2] M. Y. M. Alzoubi, The net reproductive number and bifurcation in an integro-difference system of equations, Appl. Math. Sci., 4 (2010), 191-200. [3] H. Amann, Ordinary Differential Equations: An Introduction to Nonlinear Analysis, Studies in Mathematics 13, Walter de Gruyter, Berlin-New York, 1990. doi: 10.1515/9783110853698. [4] M. Andersen, Properties of some density-dependent integrodifference equation population models, Math. Biosci., 104 (1991), 135-157.  doi: 10.1016/0025-5564(91)90034-G. [5] T. Ando, Totally positive matrices, Linear Algebra Appl., 90 (1987), 165-219.  doi: 10.1016/0024-3795(87)90313-2. [6] P. Anselone and J. Lee, Spectral properties of integral operators with nonnegative kernels, Linear Algebra Appl., 9 (1974), 67-87.  doi: 10.1016/0024-3795(74)90027-5. [7] K. Atkinson, Convergence rates for approximate eigenvalues of compact integral operators, SIAM J. Numer. Anal., 12 (1975), 213-222.  doi: 10.1137/0712020. [8] K. Atkinson, A survey of numerical methods for solving nonlinear integral equations, J. Integr. Equat. Appl., 4 (1992), 15-46.  doi: 10.1216/jiea/1181075664. [9] K. Atkinson, The Numerical Solution of Integral Equations of the Second Kind, Monographs on Applied and Comp. Mathematics 4, University Press, Cambridge, 1997.  doi: 10.1017/CBO9780511626340. [10] N. Bacaër, Periodic matrix population models: Growth rate, basic reproduction number, and entropy, Bull. Math. Biol., 71 (2009), 1781-1792.  doi: 10.1007/s11538-009-9426-6. [11] N. Bacaër and E. H. Ait Dads, On the biological interpretation of a definition for the parameter $R_0$ in periodic population models, J. Math. Biol., 65 (2012), 601-621.  doi: 10.1007/s00285-011-0479-4. [12] W.-J. Beyn, T. Hüls and M.-C. Samtenschnieder., On $r$-periodic orbits of $k$-periodic maps, J. Difference Equ. Appl., 14 (2008), 865-887.  doi: 10.1080/10236190801940010. [13] J. Bramburger and F. Lutscher, Analysis of integrodifference equations with a separable dispersal kernel, Acta Applicandae Mathematicae, 161 (2019), 127-151.  doi: 10.1007/s10440-018-0207-9. [14] F. Brauer and C. Castillo-Chavez, Mathematical Models in Population Biology and Epidemiology, Second edition. Texts in Applied Mathematics, 40. Springer, New York, 2012. doi: 10.1007/978-1-4614-1686-9. [15] B. Buffoni and J. F. Toland, Analytic Theory of Global Bifurcation: An Introduction, University Press, Princeton NJ, 2003.  doi: 10.1515/9781400884339. [16] D. Cohn, Measure Theory, Birkhäuser, Boston etc., 1980. [17] J. M. Cushing and A. S. Ackleh, A net reproductive number for periodic matrix models, J. Biol. Dyn., 6 (2012), 166-188.  doi: 10.1080/17513758.2010.544410. [18] J. M. Cushing and S. M. Henson, Periodic matrix models for seasonal dynamics of structured populations with application to a seabird population, J. Math. Biol., 77 (2018), 1689-1720.  doi: 10.1007/s00285-018-1211-4. [19] M. Crandall and P. Rabinowitz, Bifurcation from simple eigenvalues, J. Funct. Anal., 8 (1971), 321-340.  doi: 10.1016/0022-1236(71)90015-2. [20] ————, Bifurcation, perturbation of simple eigenvalues and linearized stability, Arch. Ration. Mech. Anal., 52 (1973), 161-180.  doi: 10.1007/BF00282325. [21] S. Day, O. Junge and K. Mischaikow, A rigerous numerical method for the global dynamics of infinite-dimensional discrete dynamical systems, SIAM J. Appl. Dyn. Syst., 3(2) (2004), 117-160.  doi: 10.1137/030600210. [22] K. Deimling, Nonlinear Functional Analysis, Springer, Berlin etc., 1985. doi: 10.1007/978-3-662-00547-7. [23] G. Engeln-Müllges and F. Uhlig, Numerical Algorithms with C, Springer, Berlin etc., 1996. [24] I. Győri and M. Pituk, The converse of the theorem on stability by the first approximation for difference equations, Nonlin. Analysis (TMA), 47 (2001), 4635-4640.  doi: 10.1016/S0362-546X(01)00576-4. [25] D. P. Hardin, P. Takáč and G. F. Webb, A comparison of dispersal strategies for survival of spatially heterogeneous populations, SIAM J. Appl. Math., 48 (1988), 1396-1423.  doi: 10.1137/0148086. [26] ————, Dispersion population models discrete in time and continuous in space, J. Math. Biol., 28 (1990), 1-20.  doi: 10.1007/BF00171515. [27] G. Iooss, Bifurcation of Maps and Applications, Mathematics Studies 36, North-Holland, Amsterdam etc., 1979. [28] J. Jacobsen and T. McAdam, A boundary value problem for integrodifference population models with cyclic kernels, Discrete Contin. Dyn. Syst. (Series B), 19 (2014), 3191-3207.  doi: 10.3934/dcdsb.2014.19.3191. [29] W. Jin and H. R. Thieme, An extinction/persistence threshold for sexually reproducing populations: The cone spectral radius, Discrete Contin. Dyn. Syst. (Series B), 21 (2016), 447-470.  doi: 10.3934/dcdsb.2016.21.447. [30] T. Kato, Perturbation Theory for Linear Operators (corrected 2nd ed.), Grundlehren der mathematischen Wissenschaften 132, Springer, Berlin etc., 1980. [31] C. Kelley, Solving Nonlinear Equations with Newton's Method, Fundamentals of Algorithms 1, SIAM, Philadelphia, PA, 2003. doi: 10.1137/1.9780898718898. [32] H. Kielhöfer, Bifurcation Theory: An Introduction with Applications to PDEs (2nd ed.), Applied Mathematical Sciences 156, Springer, New York etc., 2012. doi: 10.1007/978-1-4614-0502-3. [33] M. Kot and W. M. Schaffer, Discrete-time growth-dispersal models, Math. Biosci., 80 (1986), 109-136.  doi: 10.1016/0025-5564(86)90069-6. [34] U. Krause, Positive Dynamical Systems in Discrete Time, Studies in Mathematics 62, de Gruyter, Berlin etc., 2015. doi: 10.1515/9783110365696. [35] R. Kress, Linear Integral Equations ($3$rd ed.), Applied Mathematical Sciences 82, Springer, New York etc., 2014. doi: 10.1007/978-1-4614-9593-2. [36] P. Liu, J. Shi and Y. Wang, Imperfect transcritical and pitchfork bifurcations, J. Funct. Anal., 251 (2007), 573-600.  doi: 10.1016/j.jfa.2007.06.015. [37] R. Luís, S. Elaydi and H. Oliveira, Local bifurcation in one-dimensional nonautonomous periodic difference equations, Int. J. Bifurcation Chaos, 23 (2013), 1350049, 18 pp. doi: 10.1142/S0218127413500491. [38] F. Lutscher and M. A. Lewis, Spatially-explicit matrix models, J. Math. Biol., 48 (2004), 293-324.  doi: 10.1007/s00285-003-0234-6. [39] F. Lutscher and S. Petrovskii, The importance of census times in discrete-dime growth-dispersal models, J. Biol. Dynamics, 2 (2008), 55-63.  doi: 10.1080/17513750701769899. [40] F. Lutscher, Integrodifference Equations in Spatial Ecology, Interdisciplinary Applied Mathematics 49, Springer, Cham, 2019. doi: 10.1007/978-3-030-29294-2. [41] R. H. Martin, Nonlinear Operators and Differential Equations in Banach Spaces, Pure and Applied Mathematics 11, John Wiley & Sons, Chichester etc., 1976. [42] A. Pinkus, Spectral properties of totally positive kernels and matrices, in Total Positivity and Its Applications (M. Gasca et al., eds.), Mathematics and Its Applications, 359, Kluwer, Dordrecht (1996), 477–511. doi: 10.1007/978-94-015-8674-0_23. [43] C. Pötzsche, Bifurcations in a periodic discrete-time environment, Nonlinear Analysis: Real World Applications, 14 (2013), 53-82.  doi: 10.1016/j.nonrwa.2012.05.002. [44] ————, Numerical dynamics of integrodifference equations: Basics and discretization errors in a $C^0$-setting, Appl. Math. Comput., 354 (2019), 422-443.  doi: 10.1016/j.amc.2019.02.033. [45] C. Pötzsche and E. Ruß, Reduction principle for nonautonomous integrodifference equations at work, Preprint, 2020. [46] I. K. Rana, An Introduction to Measure and Integration ($2$nd ed.), Graduate Studies in Mathematics 45, American Mathematical Society, Providence RI, 2002. doi: 10.1090/gsm/045. [47] J. R. Reimer, M. B. Bonsall and P. K. Maini, Approximating the critical domain size of integrodifference equations, Bull. Math. Biol., 78 (2016), 72-109.  doi: 10.1007/s11538-015-0129-x. [48] S. L. Robertson and J. M. Cushing, A bifurcation analysis of stage-structured density dependent integrodifference equations, J. Math. Anal. Appl., 388 (2012), 490-499.  doi: 10.1016/j.jmaa.2011.09.064. [49] J. Shi, Persistence and bifurcation of degenerate solutions, J. Funct. Anal., 169 (1999), 494-531.  doi: 10.1006/jfan.1999.3483. [50] M. Slatkin, Gene flow and selection in a cline, Genetics, 75 (1973), 733-756. [51] H. R. Thieme, On a class of Hammerstein integral equations, Manuscripta Math., 29 (1979), 49-84.  doi: 10.1007/BF01309313. [52] ————, Discrete time population dynamics on the state space of measures, Math. Biosci. ngin., 17 (2020), 1168-1217. [53] R. W. Van Kirk and M. A. Lewis, Integrodifference models for persistence in fragmented habitats, Bull. Math. Biol., 59 (1997), 107-137. [54] D. S. Watkins, The Matrix Eigenvalue Problem –- GR and Krylov Subspace Methods, SIAM, Philadelphia, PA, 2007. doi: 10.1137/1.9780898717808. [55] R. Weiss, On the approximation of fixed points of nonlinear compact operators, SIAM J. Numer. Anal., 11 (1974), 550-553.  doi: 10.1137/0711046. [56] E. Zeidler, Applied Functional Analysis: Main Principles and their Applications, Applied Mathematical Sciences 109, Springer, Heidelberg, 1995. [57] X.-Q. Zhao, Dynamical Systems in Population Biology (2nd ed.), CMS Books in Mathematics, Springer, Cham, 2017. doi: 10.1007/978-3-319-56433-3. [58] Y. Zhou and W. F. Fagan, A discrete-time model for population persistence in habitats with time-varying sizes, J. Math. Biol., 75 (2017), 649-704.  doi: 10.1007/s00285-017-1095-8.

show all references

##### References:
 [1] C. Aarset and C. Pötzsche, Bifurcations in periodic integrodifference equations in $C(\Omega)$ II: Discrete torus bifurcations, Commun. Pure Appl. Anal., 19 (2020), 1847-1874. [2] M. Y. M. Alzoubi, The net reproductive number and bifurcation in an integro-difference system of equations, Appl. Math. Sci., 4 (2010), 191-200. [3] H. Amann, Ordinary Differential Equations: An Introduction to Nonlinear Analysis, Studies in Mathematics 13, Walter de Gruyter, Berlin-New York, 1990. doi: 10.1515/9783110853698. [4] M. Andersen, Properties of some density-dependent integrodifference equation population models, Math. Biosci., 104 (1991), 135-157.  doi: 10.1016/0025-5564(91)90034-G. [5] T. Ando, Totally positive matrices, Linear Algebra Appl., 90 (1987), 165-219.  doi: 10.1016/0024-3795(87)90313-2. [6] P. Anselone and J. Lee, Spectral properties of integral operators with nonnegative kernels, Linear Algebra Appl., 9 (1974), 67-87.  doi: 10.1016/0024-3795(74)90027-5. [7] K. Atkinson, Convergence rates for approximate eigenvalues of compact integral operators, SIAM J. Numer. Anal., 12 (1975), 213-222.  doi: 10.1137/0712020. [8] K. Atkinson, A survey of numerical methods for solving nonlinear integral equations, J. Integr. Equat. Appl., 4 (1992), 15-46.  doi: 10.1216/jiea/1181075664. [9] K. Atkinson, The Numerical Solution of Integral Equations of the Second Kind, Monographs on Applied and Comp. Mathematics 4, University Press, Cambridge, 1997.  doi: 10.1017/CBO9780511626340. [10] N. Bacaër, Periodic matrix population models: Growth rate, basic reproduction number, and entropy, Bull. Math. Biol., 71 (2009), 1781-1792.  doi: 10.1007/s11538-009-9426-6. [11] N. Bacaër and E. H. Ait Dads, On the biological interpretation of a definition for the parameter $R_0$ in periodic population models, J. Math. Biol., 65 (2012), 601-621.  doi: 10.1007/s00285-011-0479-4. [12] W.-J. Beyn, T. Hüls and M.-C. Samtenschnieder., On $r$-periodic orbits of $k$-periodic maps, J. Difference Equ. Appl., 14 (2008), 865-887.  doi: 10.1080/10236190801940010. [13] J. Bramburger and F. Lutscher, Analysis of integrodifference equations with a separable dispersal kernel, Acta Applicandae Mathematicae, 161 (2019), 127-151.  doi: 10.1007/s10440-018-0207-9. [14] F. Brauer and C. Castillo-Chavez, Mathematical Models in Population Biology and Epidemiology, Second edition. Texts in Applied Mathematics, 40. Springer, New York, 2012. doi: 10.1007/978-1-4614-1686-9. [15] B. Buffoni and J. F. Toland, Analytic Theory of Global Bifurcation: An Introduction, University Press, Princeton NJ, 2003.  doi: 10.1515/9781400884339. [16] D. Cohn, Measure Theory, Birkhäuser, Boston etc., 1980. [17] J. M. Cushing and A. S. Ackleh, A net reproductive number for periodic matrix models, J. Biol. Dyn., 6 (2012), 166-188.  doi: 10.1080/17513758.2010.544410. [18] J. M. Cushing and S. M. Henson, Periodic matrix models for seasonal dynamics of structured populations with application to a seabird population, J. Math. Biol., 77 (2018), 1689-1720.  doi: 10.1007/s00285-018-1211-4. [19] M. Crandall and P. Rabinowitz, Bifurcation from simple eigenvalues, J. Funct. Anal., 8 (1971), 321-340.  doi: 10.1016/0022-1236(71)90015-2. [20] ————, Bifurcation, perturbation of simple eigenvalues and linearized stability, Arch. Ration. Mech. Anal., 52 (1973), 161-180.  doi: 10.1007/BF00282325. [21] S. Day, O. Junge and K. Mischaikow, A rigerous numerical method for the global dynamics of infinite-dimensional discrete dynamical systems, SIAM J. Appl. Dyn. Syst., 3(2) (2004), 117-160.  doi: 10.1137/030600210. [22] K. Deimling, Nonlinear Functional Analysis, Springer, Berlin etc., 1985. doi: 10.1007/978-3-662-00547-7. [23] G. Engeln-Müllges and F. Uhlig, Numerical Algorithms with C, Springer, Berlin etc., 1996. [24] I. Győri and M. Pituk, The converse of the theorem on stability by the first approximation for difference equations, Nonlin. Analysis (TMA), 47 (2001), 4635-4640.  doi: 10.1016/S0362-546X(01)00576-4. [25] D. P. Hardin, P. Takáč and G. F. Webb, A comparison of dispersal strategies for survival of spatially heterogeneous populations, SIAM J. Appl. Math., 48 (1988), 1396-1423.  doi: 10.1137/0148086. [26] ————, Dispersion population models discrete in time and continuous in space, J. Math. Biol., 28 (1990), 1-20.  doi: 10.1007/BF00171515. [27] G. Iooss, Bifurcation of Maps and Applications, Mathematics Studies 36, North-Holland, Amsterdam etc., 1979. [28] J. Jacobsen and T. McAdam, A boundary value problem for integrodifference population models with cyclic kernels, Discrete Contin. Dyn. Syst. (Series B), 19 (2014), 3191-3207.  doi: 10.3934/dcdsb.2014.19.3191. [29] W. Jin and H. R. Thieme, An extinction/persistence threshold for sexually reproducing populations: The cone spectral radius, Discrete Contin. Dyn. Syst. (Series B), 21 (2016), 447-470.  doi: 10.3934/dcdsb.2016.21.447. [30] T. Kato, Perturbation Theory for Linear Operators (corrected 2nd ed.), Grundlehren der mathematischen Wissenschaften 132, Springer, Berlin etc., 1980. [31] C. Kelley, Solving Nonlinear Equations with Newton's Method, Fundamentals of Algorithms 1, SIAM, Philadelphia, PA, 2003. doi: 10.1137/1.9780898718898. [32] H. Kielhöfer, Bifurcation Theory: An Introduction with Applications to PDEs (2nd ed.), Applied Mathematical Sciences 156, Springer, New York etc., 2012. doi: 10.1007/978-1-4614-0502-3. [33] M. Kot and W. M. Schaffer, Discrete-time growth-dispersal models, Math. Biosci., 80 (1986), 109-136.  doi: 10.1016/0025-5564(86)90069-6. [34] U. Krause, Positive Dynamical Systems in Discrete Time, Studies in Mathematics 62, de Gruyter, Berlin etc., 2015. doi: 10.1515/9783110365696. [35] R. Kress, Linear Integral Equations ($3$rd ed.), Applied Mathematical Sciences 82, Springer, New York etc., 2014. doi: 10.1007/978-1-4614-9593-2. [36] P. Liu, J. Shi and Y. Wang, Imperfect transcritical and pitchfork bifurcations, J. Funct. Anal., 251 (2007), 573-600.  doi: 10.1016/j.jfa.2007.06.015. [37] R. Luís, S. Elaydi and H. Oliveira, Local bifurcation in one-dimensional nonautonomous periodic difference equations, Int. J. Bifurcation Chaos, 23 (2013), 1350049, 18 pp. doi: 10.1142/S0218127413500491. [38] F. Lutscher and M. A. Lewis, Spatially-explicit matrix models, J. Math. Biol., 48 (2004), 293-324.  doi: 10.1007/s00285-003-0234-6. [39] F. Lutscher and S. Petrovskii, The importance of census times in discrete-dime growth-dispersal models, J. Biol. Dynamics, 2 (2008), 55-63.  doi: 10.1080/17513750701769899. [40] F. Lutscher, Integrodifference Equations in Spatial Ecology, Interdisciplinary Applied Mathematics 49, Springer, Cham, 2019. doi: 10.1007/978-3-030-29294-2. [41] R. H. Martin, Nonlinear Operators and Differential Equations in Banach Spaces, Pure and Applied Mathematics 11, John Wiley & Sons, Chichester etc., 1976. [42] A. Pinkus, Spectral properties of totally positive kernels and matrices, in Total Positivity and Its Applications (M. Gasca et al., eds.), Mathematics and Its Applications, 359, Kluwer, Dordrecht (1996), 477–511. doi: 10.1007/978-94-015-8674-0_23. [43] C. Pötzsche, Bifurcations in a periodic discrete-time environment, Nonlinear Analysis: Real World Applications, 14 (2013), 53-82.  doi: 10.1016/j.nonrwa.2012.05.002. [44] ————, Numerical dynamics of integrodifference equations: Basics and discretization errors in a $C^0$-setting, Appl. Math. Comput., 354 (2019), 422-443.  doi: 10.1016/j.amc.2019.02.033. [45] C. Pötzsche and E. Ruß, Reduction principle for nonautonomous integrodifference equations at work, Preprint, 2020. [46] I. K. Rana, An Introduction to Measure and Integration ($2$nd ed.), Graduate Studies in Mathematics 45, American Mathematical Society, Providence RI, 2002. doi: 10.1090/gsm/045. [47] J. R. Reimer, M. B. Bonsall and P. K. Maini, Approximating the critical domain size of integrodifference equations, Bull. Math. Biol., 78 (2016), 72-109.  doi: 10.1007/s11538-015-0129-x. [48] S. L. Robertson and J. M. Cushing, A bifurcation analysis of stage-structured density dependent integrodifference equations, J. Math. Anal. Appl., 388 (2012), 490-499.  doi: 10.1016/j.jmaa.2011.09.064. [49] J. Shi, Persistence and bifurcation of degenerate solutions, J. Funct. Anal., 169 (1999), 494-531.  doi: 10.1006/jfan.1999.3483. [50] M. Slatkin, Gene flow and selection in a cline, Genetics, 75 (1973), 733-756. [51] H. R. Thieme, On a class of Hammerstein integral equations, Manuscripta Math., 29 (1979), 49-84.  doi: 10.1007/BF01309313. [52] ————, Discrete time population dynamics on the state space of measures, Math. Biosci. ngin., 17 (2020), 1168-1217. [53] R. W. Van Kirk and M. A. Lewis, Integrodifference models for persistence in fragmented habitats, Bull. Math. Biol., 59 (1997), 107-137. [54] D. S. Watkins, The Matrix Eigenvalue Problem –- GR and Krylov Subspace Methods, SIAM, Philadelphia, PA, 2007. doi: 10.1137/1.9780898717808. [55] R. Weiss, On the approximation of fixed points of nonlinear compact operators, SIAM J. Numer. Anal., 11 (1974), 550-553.  doi: 10.1137/0711046. [56] E. Zeidler, Applied Functional Analysis: Main Principles and their Applications, Applied Mathematical Sciences 109, Springer, Heidelberg, 1995. [57] X.-Q. Zhao, Dynamical Systems in Population Biology (2nd ed.), CMS Books in Mathematics, Springer, Cham, 2017. doi: 10.1007/978-3-319-56433-3. [58] Y. Zhou and W. F. Fagan, A discrete-time model for population persistence in habitats with time-varying sizes, J. Math. Biol., 75 (2017), 649-704.  doi: 10.1007/s00285-017-1095-8.
First critical values $\alpha_i^0$ for bifurcations from the trivial branch (left). Nontrivial branch $\phi_0^0$ of the primary transcritical bifurcation at $\alpha_0^0\approx 1.74$ for the Beverton-Holt growth-dispersal IDE with right-hand side (5.12), Laplace kernel (3.10) and $a = 1$, $L = 2$ (center). Total population over $\alpha\in[0,6]$ along $\phi_0^0$ (right)
First critical values $\alpha_i^0$ for bifurcations from the trivial branch (left). Nontrivial branch $\phi_0^0$ of the primary transcritical bifurcation at $\alpha_0^0\approx 1.74$ for the Beverton-Holt dispersal-growth IDE with right-hand side (5.17), Laplace kernel (3.10) and $a = 1$, $L = 1$ (center). Total population over $\alpha\in[0,6]$ along $\phi_0^0$ (right)
First critical values $\alpha_i^1$ for bifurcations along the primary branch $\phi_0^0$ (left). The $\alpha$-dependence of the corresponding eigenvalues $\lambda^1_{i-1}(\alpha)$ for $\alpha\geq 0.1$ (center). Period doubling cascade for the Ricker IDE with right-hand side (5.18) and $\alpha\in[0,40]$ for the Gauß kernel (5.19) with $a=1$, $L=2$ (right)
Equilibrium branches $\phi^\pm(aL)$ as functions of the dispersal parameter $\alpha=aL$ (left). Four largest eigenvalues $\lambda^\pm(aL)$ along these two branches of nontrivial solutions to (3.11) (right)
Subcritical ($\tfrac{g_{20}}{g_{11}}>0$) and supercritical ($\tfrac{g_{20}}{g_{11}}<0$) fold bifurcation of $\theta$-periodic solutions to $\left(\Delta_{\alpha}\right)$ described in Thm. 4.2, as well as the exchange of stability between the branches $\Gamma^+$ and $\Gamma^-$ from unstable (dashed line) to exponentially stable (solid) covered in Cor. 4.3
Transcritical bifurcation of $\theta$-periodic solutions to $\left(\Delta_{\alpha}\right)$ from a branch $\Gamma_1$ into $\Gamma_2$ described in Prop. 4.6, as well as the exchange of stability from unstable (dashed line) to exponentially stable (solid)
Subcritical $(\bar g/g_{11}>0)$ and supercritical $(\bar g/g_{11}<0)$ pitchfork bifurcation of $\theta$-periodic solutions to $\left(\Delta_{\alpha}\right)$ from a branch $\Gamma_1$ into $\Gamma_2$ described in Prop. 4.7, as well as the exchange of stability from unstable (dashed line) to exponentially stable (solid)
Branch of the subcritical fold bifurcation for $\left(\Delta_{\alpha}\right)$ with right-hand side (5.2) and kernel (5.1) (left). Total population over $\alpha\in[0.0,0.3]$ with $a = \tfrac{1}{4}$, $L = 2$ along the branch (right)
Schematic bifurcation diagrams for the cosine kernel (5.1) with $aL\leq\tfrac{1}{2}$ illustrating branches of $\theta$-periodic solutions: Ex. 4 has a subcritical fold bifurcation of fixed points at $(\phi^\ast,\alpha^\ast)$ (left). After a supercritical period doubling at $(0,\alpha_0^0)$, Ex. 5 has a supercritical pitchfork bifurcation of $2$-periodic solutions at $(\phi_\pm(\alpha_1^0),\alpha_1^0)$ (right). Fixed point branches are solid $(\theta = 1)$, branches of $2$-periodic solutions are dashed $(\theta = 2)$ and $4$-periodic solutions are indicated by dotted lines $(\theta = 4)$
Branch $\phi_1^0$ of the supercritical pitchfork bifurcation at $\alpha_1^0\approx 5.12$ for the Beverton-Holt growth-dispersal IDE with right-hand side (5.12), Laplace kernel (3.10) and $a = 1$, $L = 2$ (left). Total population over $\alpha\in[\alpha_1^0,7]$ along $\phi_1^0$ (right)
Branch $\phi_2^0$ of the transcritical bifurcation at $\alpha_2^0\approx 12.73$ for the Beverton-Holt growth-dispersal IDE with right-hand side (5.12), Laplace kernel (3.10) and $a = 1$, $L = 2$ as part of a fold (left). Total population over parameters $\alpha\in[12.4, 15]$ reflecting a fold in $\phi_2^0$ (right)
Branch $\phi_1^0$ of the supercritical pitchfork bifurcation at $\alpha_1^0\approx 5.12$ for the Beverton-Holt dispersal-growth IDE with right-hand side (5.17), Laplace kernel (3.10) and $a = 1$, $L = 2$ (left). Total population over $\alpha\in[5,6]$ along $\phi_1^0$ (right)
Branch $\phi_2^0$ of the transcritical bifurcation at $\alpha_2^0\approx 12.73$ for the Beverton-Holt dispersal-growth IDE with right-hand side (5.17), Laplace kernel (3.10) and $a=1$, $L=2$ as part of a fold (left). Total population over parameters $\alpha\in[12,13]$ reflecting a fold in $\phi_2^0$ (right)
Schematic bifurcation diagrams: Branches of $\theta$-periodic solutions in the Beverton-Holt IDE having the right-hand sides (5.12)/(5.17), $\alpha\in[0,50]$ and the Laplace kernel (5.19) with $a=1$, $L=2$ (left), as well as IDE with right-hand side (5.18) and $\alpha\in[0,3000]$ (logarithmic axis) for the Gauß kernel (5.19) with $a=1$, $L=2$ (right). Fixed point branches are solid $(\theta=1)$, branches of $2$-periodic solutions are dashed $(\theta=2)$ and $4$-periodic solutions are indicated by dotted lines $(\theta=4)$
First critical values $\alpha_i^0$ for bifurcations from the trivial branch (left). The $\alpha$-dependence of the corresponding eigenvalues $\lambda_{i-1}^0(\alpha)$ (center). Primary transcritical bifurcation of the branch $\phi_0^0$ at $\alpha^0_0\approx 1.36$ for the Gauß kernel (5.19) with $a=1$, $L=2$ (right)
Coefficients in commonly used growth functions $\hat g$, $c>0$
 growth function $\hat g(z)$ $c_2$ $d_2$ $c_3$ $d_3$ logistic $z(1-z)$ $-2$ $-2$ $0$ $0$ Hassell $\tfrac{z}{(1+z)^c}$ $-2c$ $-2c$ $3(1+c)c$ $3(1+c)c$ Ricker $ze^{-z}$ $-2$ $-2$ $3$ $3$
 growth function $\hat g(z)$ $c_2$ $d_2$ $c_3$ $d_3$ logistic $z(1-z)$ $-2$ $-2$ $0$ $0$ Hassell $\tfrac{z}{(1+z)^c}$ $-2c$ $-2c$ $3(1+c)c$ $3(1+c)c$ Ricker $ze^{-z}$ $-2$ $-2$ $3$ $3$
Quadrature rules (B.1) with $h: = \tfrac{b-a}{n}$
 rule nodes $\eta_j$ weights $w_j$ $r$ $N_n$ midpoint $a+h(j-\tfrac{1}{2})$ $h$ $2$ $n$ trapezoidal $a+h(j-1)$ $\tfrac{h}{2}\text{ for }j\in\left\{{1,n+1}\right\}$ $2$ $n+1$ $h$ else Chebyshev $a+(j-\tfrac{\sqrt{3}+1}{2\sqrt{3}})h$ for $j\leq n$ $\tfrac{h}{2}$ $4$ $2n$ $a+(j-n+\tfrac{\sqrt{3}-1}{2\sqrt{3}})h$ for n < j
 rule nodes $\eta_j$ weights $w_j$ $r$ $N_n$ midpoint $a+h(j-\tfrac{1}{2})$ $h$ $2$ $n$ trapezoidal $a+h(j-1)$ $\tfrac{h}{2}\text{ for }j\in\left\{{1,n+1}\right\}$ $2$ $n+1$ $h$ else Chebyshev $a+(j-\tfrac{\sqrt{3}+1}{2\sqrt{3}})h$ for $j\leq n$ $\tfrac{h}{2}$ $4$ $2n$ $a+(j-n+\tfrac{\sqrt{3}-1}{2\sqrt{3}})h$ for n < j
 [1] Zhiqin Qiao, Deming Zhu, Qiuying Lu. Bifurcation of a heterodimensional cycle with weak inclination flip. Discrete and Continuous Dynamical Systems - B, 2012, 17 (3) : 1009-1025. doi: 10.3934/dcdsb.2012.17.1009 [2] Satoshi Kosugi, Yoshihisa Morita, Shoji Yotsutani. A complete bifurcation diagram of the Ginzburg-Landau equation with periodic boundary conditions. Communications on Pure and Applied Analysis, 2005, 4 (3) : 665-682. doi: 10.3934/cpaa.2005.4.665 [3] Jean-Philippe Lessard, Evelyn Sander, Thomas Wanner. Rigorous continuation of bifurcation points in the diblock copolymer equation. Journal of Computational Dynamics, 2017, 4 (1&2) : 71-118. doi: 10.3934/jcd.2017003 [4] Jongmin Han, Masoud Yari. Dynamic bifurcation of the complex Swift-Hohenberg equation. Discrete and Continuous Dynamical Systems - B, 2009, 11 (4) : 875-891. doi: 10.3934/dcdsb.2009.11.875 [5] Jean-François Rault. A bifurcation for a generalized Burgers' equation in dimension one. Discrete and Continuous Dynamical Systems - S, 2012, 5 (3) : 683-706. doi: 10.3934/dcdss.2012.5.683 [6] Andrus Giraldo, Bernd Krauskopf, Hinke M. Osinga. Computing connecting orbits to infinity associated with a homoclinic flip bifurcation. Journal of Computational Dynamics, 2020, 7 (2) : 489-510. doi: 10.3934/jcd.2020020 [7] Fang Wu, Lihong Huang, Jiafu Wang. Bifurcation of the critical crossing cycle in a planar piecewise smooth system with two zones. Discrete and Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021264 [8] Jongmin Han, Chun-Hsiung Hsia. Dynamical bifurcation of the two dimensional Swift-Hohenberg equation with odd periodic condition. Discrete and Continuous Dynamical Systems - B, 2012, 17 (7) : 2431-2449. doi: 10.3934/dcdsb.2012.17.2431 [9] Qigang Yuan, Jingli Ren. Periodic forcing on degenerate Hopf bifurcation. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2857-2877. doi: 10.3934/dcdsb.2020208 [10] Yuncherl Choi, Taeyoung Ha, Jongmin Han, Doo Seok Lee. Bifurcation and final patterns of a modified Swift-Hohenberg equation. Discrete and Continuous Dynamical Systems - B, 2017, 22 (7) : 2543-2567. doi: 10.3934/dcdsb.2017087 [11] Tatsuki Mori, Kousuke Kuto, Tohru Tsujikawa, Shoji Yotsutani. Representation formulas of solutions and bifurcation sheets to a nonlocal Allen-Cahn equation. Discrete and Continuous Dynamical Systems, 2020, 40 (8) : 4907-4925. doi: 10.3934/dcds.2020205 [12] Joel Kübler, Tobias Weth. Spectral asymptotics of radial solutions and nonradial bifurcation for the Hénon equation. Discrete and Continuous Dynamical Systems, 2020, 40 (6) : 3629-3656. doi: 10.3934/dcds.2020032 [13] Yuqian Zhou, Qian Liu. Reduction and bifurcation of traveling waves of the KdV-Burgers-Kuramoto equation. Discrete and Continuous Dynamical Systems - B, 2016, 21 (6) : 2057-2071. doi: 10.3934/dcdsb.2016036 [14] Tomás Caraballo, Renato Colucci, Luca Guerrini. Bifurcation scenarios in an ordinary differential equation with constant and distributed delay: A case study. Discrete and Continuous Dynamical Systems - B, 2019, 24 (6) : 2639-2655. doi: 10.3934/dcdsb.2018268 [15] Jungho Park. Bifurcation and stability of the generalized complex Ginzburg--Landau equation. Communications on Pure and Applied Analysis, 2008, 7 (5) : 1237-1253. doi: 10.3934/cpaa.2008.7.1237 [16] Yuncherl Choi, Jongmin Han, Chun-Hsiung Hsia. Bifurcation analysis of the damped Kuramoto-Sivashinsky equation with respect to the period. Discrete and Continuous Dynamical Systems - B, 2015, 20 (7) : 1933-1957. doi: 10.3934/dcdsb.2015.20.1933 [17] José Caicedo, Alfonso Castro, Arturo Sanjuán. Bifurcation at infinity for a semilinear wave equation with non-monotone nonlinearity. Discrete and Continuous Dynamical Systems, 2017, 37 (4) : 1857-1865. doi: 10.3934/dcds.2017078 [18] Toshiyuki Ogawa, Takashi Okuda. Bifurcation analysis to Swift-Hohenberg equation with Steklov type boundary conditions. Discrete and Continuous Dynamical Systems, 2009, 25 (1) : 273-297. doi: 10.3934/dcds.2009.25.273 [19] Patrick M. Fitzpatrick, Jacobo Pejsachowicz. Branching and bifurcation. Discrete and Continuous Dynamical Systems - S, 2019, 12 (7) : 1955-1975. doi: 10.3934/dcdss.2019127 [20] Tian Hou, Yi Wang, Xizhuang Xie. Instability and bifurcation of a cooperative system with periodic coefficients. Electronic Research Archive, 2021, 29 (5) : 3069-3079. doi: 10.3934/era.2021026

2021 Impact Factor: 1.497


text:
Browse Questions

# A spectral line in the spectrum of $H$-atom has a wave number of $15222.22cm^{-1}$. What transition is responsible for this radiation? (Rydberg constant $R=1.096\times 10^5cm^{-1}$)

$(a)\;3\qquad(b)\;1\qquad(c)\;2\qquad(d)\;4$

$\lambda=\large\frac{1}{\bar v}=\frac{1}{15222.22} = 6.569\times 10^{-5}cm = 6569\overset{\circ}{A}$
Clearly, the spectral line lies in the visible region (i.e.) in Balmer series
Hence, $n_1=2$
Using the relation for wave number for H-atom
$\Large\bar v=\frac{1}{\lambda}(\large\frac{1}{n_1^2}-\frac{1}{n_2^2})$
$\Rightarrow 15222.22=1.096\times 10^5\Large(\frac{1}{2^2}-\frac{1}{(n_2)^2})$
$\Rightarrow n_2=3$
Hence (a) is the correct answer.
edited Mar 19, 2014


text:
# Do these 2 KSA shortcuts weaken RC4?

Alice securely gives Bob a secret key so they can exchange 10 different messages encrypted with RC4. (Messages will include a counter for uniqueness and a MAC for authentication.) For each message exchange, Alice and Bob both start by permuting the standard byte array using the secret key (ie, the "KSA" key-scheduling algorithm, per Wikipedia):

for i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod keylength]) mod 256
swap values of S[i] and S[j]
endfor

At this point, Alice and Bob have each computed identical S[] arrays, and the secret key is no longer used by subsequent RC4 steps.

Shortcut 1: Alice decides that instead of securely sending Bob the secret key and making him do the KSA step for every message exchange, she'll compute the S[] array, securely send him the 256-byte array instead of the secret key to begin with, and from then on each time they need to encrypt/decrypt they'll both skip the KSA step to save time and just start with Alice's precomputed S[] array.

Shortcut 2: After using the above algorithm to compute the initial S[] array she had planned to send to Bob instead of the secret key, Alice realizes the KSA step seems to basically just want to scramble the S[] array. So instead of scrambling the array based on a key, she relies on the operating system random() function and just computes...

for i from 0 to 255
S[i] := i
endfor
for i from 0 to 255
swap(S[i], S[random(0..255)]) // swap S[i] with some arbitrary S[]
endfor

...and securely sends Bob her "randomly" scrambled array that doesn't even use a key.

Do those 2 shortcuts weaken RC4?

-

Regarding #1:

You don't lose anything with regards to the algorithm itself. The algorithm to go from the key to the key schedule (KS) is deterministic and well known, so anyone who gets the key can easily get the KS too. The actual algorithm itself isn't made less secure by communicating the KS instead of the key.

However, relying on the KS instead of the key makes things more practically difficult.

The scheme that you describe isn't secure because the encryption isn't randomized. All symmetric key encryption needs to be randomized. You are including a unique counter in the output, and some variations of that work for block ciphers, but that won't randomize the entire ciphertext for your stream cipher. For a stream cipher, the randomization occurs as a unique nonce that is combined with the key to generate a unique key stream that is in turn used to create a unique ciphertext.

Making your scheme secure could be done by adding nonces to the key for each encryption. So exchanging the KS itself actually makes using good encryption harder in this case because you can't simply exchange a new nonce for encryption, you have to exchange a whole new KS to include the change from the nonce. The nonce can be publicly exchanged and is short, but the KS must be kept secret and is longer. So then the question becomes, how are you securely exchanging the updated KSs? You might be able to securely agree upon the first key, but can you continuously agree upon new keys securely? Would you have to set all the KSs in advance when the original key is agreed upon? It gets messy.

If you are trying to optimize encryption, the standard way to do it is to exchange the key and then cache the KS on all the clients that use it. You would have to compute the KS once per client, but the RC4 KS is really short and shouldn't be a speed issue on any semi-modern platform. (Two loops of 256 count, an average of about three memory lookups and a few additions per loop. How bad could that be as a one-time performance penalty?) This way the optimization is abstracted within each client and you still have normal key exchange features.

So for your scheme, you shouldn't re-start the encryption for each message unless you want to include unique nonces for each reset. To avoid the nonces, you could just keep using the continued output stream of RC4 for all the messages (somehow ensuring that each client is synchronized as to how far into the stream they are). Either way would be better than the current scheme.

I know most of that isn't directly related to your question, but even though your proposal isn't inherently more insecure, it does make fixing your insecure protocol more difficult.

Regarding #2:

Note that, basically, you replaced

j := (j + S[i] + key[i mod keylength]) mod 256

with

j := random(0..255)

Assume for a moment that keylength is 256. Now consider the case that key and random() comes from a high quality entropy source, that is key is effectively just a random 256 byte string of the same quality that 256 bytes of random() would produce. The addition of constants and some slight "self-modification" from S[i] won't improve the quality of key. So for a good 256 byte random key, your scheme hasn't changed anything. In fact, you can calculate the effective key that your new scheme would create:

for i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
temp = random(0..255)
k[i] := temp - j - S[i]
j = temp
swap(S[i], S[j])
endfor

That is to say, the key k here would have produced the same KS as your scheme (if given the same values from random()). This calculated key is still as secure as the output from random(). So instead of pre-generating a key to use, you're just generating it on the fly. There's really no difference.

(If the feedback-style role of j and S[i] concerns you, remember that we assumed that random() was a good entropy source. At best these variables are adding a random value to the output of random(), but that output was already securely random so no quality is added or removed. At worst they are adding constant values, and again it doesn't change anything.)

So your second scheme is the equivalent of just generating a 256 byte random key to begin with, and that's the best key that RC4 can use. Given that your scheme doesn't improve on the maximal security bounds of RC4, it doesn't really add anything. You can select the quality of the KS by choosing an appropriately strong key. If you want maximum security, just generate a high quality (256 byte) key. (Possibly via the call to random(), if you trust it to generate keys.)

Note:

Everything here assumes that you can distribute the initial key securely and that you trust the output of this random() function. It seems like you do assume this, but keep in mind that those are two very big assumptions. Ensure that your random() call is a cryptographically secure call, preferably to something like CryptGenRandom() on Windows or /dev/random on *nix.

-

The obvious problem with Shortcut 1 is that the same keystream will be used to encrypt all the messages. That is, an attacker can exclusive-or two ciphertexts together, and the result will be the exclusive-or of the two plaintexts; this may very well allow the attacker to recover both messages. How easy this is depends on the language the messages are in; if we assume they are in ASCII-English, this is fairly straight-forwarding as long as the messages aren't extremely brief.

There are two obvious problems with Shortcut 2:

• How cryptographically secure is the operating system "random" function? Quite often, such operating system functions are only statistically random, this might not be good enough.

• You say that Alice "securely" sends Bob the array; is she sending a separate array for each message? If so, why doesn't she use that secure method to send the message? If not (that is, she reused the same array for different messages), she runs into exactly the same problem as Shortcut 1.

Also, in shortcut 2, your pseudocode says "Assign a random S[] element to S[i]", while your comment says to swap them. Which do you mean? What you really want to do is swap the elements (it's important that S[] remain a permutation).

-
I think your concern with Shortcut 1 missed the point. Regardless of how many times they use the same key or switch to a new key, the question concerns sharing the precomputed array instead of sharing the key. Is it not true that giving Bob the array is equivalent to giving Bob the key, and Bob then doesn't have to compute the array? Any time you want to give Bob a key, how is it worse to give him the equivalent array instead? –  Witness Protection ID 44583292 Jun 5 '12 at 18:25
Re Shortcut 2, you ask "how cryptographically secure" the OS function is. The standard KSA swapping seems pseudorandom at best. If random() is "only statistically random", isn't that still at least as good as the standard KSA swapping? If a func like random() is used to scramble the array, what subsequent test could be used to determine the result is worse or better than the standard KSA swapping? Or, what's a known random() func that would be at least as good but possibly simpler than the standard KSA swapping? Is the standard swap trying to do something other than randomly scramble S[]? –  Witness Protection ID 44583292 Jun 5 '12 at 18:28
You ask if Alice is sending a separate array for each message. Just assume she's sending the array as frequently as she would be sending a new key. The point is not how or how often they are managing to securely exchange a key, the point is can't Alice simply send the array instead of the key so Bob can skip the KSA? As for the swapping, I've fixed the pseudocode. –  Witness Protection ID 44583292 Jun 5 '12 at 18:28
@mike: Obviously, you never want to reuse the exact same RC4 key to encrypt two different messages. One thing you can do (if you have a counter) is compute Hash( actual_key, counter ), and use that as the RC4 key. However, if you precompute the permutation, you don't have the opportunity –  poncho Jun 5 '12 at 18:29
@mike It might miss the point of your question, but is an important consideration for using RC4 (and ciphers without initialization vectors in general): Never encrypt more than one message with the same key. –  Paŭlo Ebermann Jun 5 '12 at 18:30


text:
# Signals and Systems - Alternate notation for systems of signals?

I specifically have a problem with certain notation used to describe systems of signals (context: Signals and Systems by Oppenheim, et. al.); from the Center for Computer Research in Music and Acoustics (Stanford University):

The current material I am learning with likes to use something similar along these lines. Particularly, in proofs, I have a hard time differentiating between the system proper and the inputs to the system, as the system is not allocated a specific variable to represent it before evaluation/substitution/abstraction or "binding."

Can I represent a system with a more function-like notation: e.g.:

$$H[f(x)] = f(2x)$$

To me, this seems a lot clearer, but it seems to break down in the context of ordinary differential equations:

$$\frac{dy(t)}{dt} + (sin\ t)(y(t)) = 3x(t)$$

Would the following be a good notation for the above?

$$H[y(t), x(t)] = \{ \frac{dy(t)}{dt} + (sin\ t)(y(t)) = 3x(t) \}$$

Or, am I misunderstanding something that is causing me to "not get" the notation?

I am looking for a clear notation that expresses the signals and their dependencies clearly.

I am not sure what you exactly mean.

In general, $x[n]$ represents the input of the system, and y[n] the output. (Except for the specific illustration)

We always use $H(\cdot)$ to represent a filter. ( But you can use it to represent a general transform , just the notation)

If you define the function $H(\cdot)$ with the first argument $x[n]$ and the second one $y[n]$, then it seems no problem.

• Is there a difference between a filter/transform and a system? I once asked whether the Fourier transform is a system, but I couldn't understand the answer... – CinchBlue Sep 23 '16 at 9:05
• @VermillionAzure The difference bewteen the output and input is the transform( system transfers $x[n]$ to $y[n]$) . Filter is one of the transforms – stander Qiu Sep 23 '16 at 9:08
• Can you restate that? It's not clear to me what you're trying to say. – CinchBlue Sep 23 '16 at 9:11
• Fourier Transform is not a system. It does not transfers the $x[n]$ to other things. It is a mathematical tool to calculate the spectrum, which is another angle to look at the signal – stander Qiu Sep 23 '16 at 9:12
• @VermillionAzure I am very sorry that I misunderstand the 'transfer'.( not native speaker) . Transform means changes. – stander Qiu Sep 23 '16 at 9:15

The problem is that in practice a linear systems is not "naturally" given by an explicit function $H(x) = y$ that maps an input signal $x$ to an output signal $y$, but rather an implicit relation like your example: $$y'(t) + \sin t \, y(t) = 3 x(t), \quad y(0) = y_0 \quad (1)$$ Provided this equation has a unique solution, this equation represents a linear system $H$ that maps an input signal $x$ to an output $y$, but we have no explicit formula for $H$ in this case.

To answer your question, I think the best notation is to stick with (1), and simply state which signal is the input and which signal is the output if you need to be extra clear.

• One problem I have with the notation is that having to specify what the input/output signal per "instantiation" or specialization of the general equation to specific signals (e.g. x1 into x and y1 into y) is that we lose the information that specialization of the general equation is derived from that same system. Also, isn't H in this case simply the entirely of (1) minus the initial condition definition? Or does this cause a problem with substitution? – CinchBlue Sep 23 '16 at 9:22


text:
# Arithmetic Question Involving Quantum Physics

1. The problem statement, all variables and given/known data

Two adjacent allowed energies of an electron in a one-dimensional box are 2.0 eV and 4.5 eV. What is the length of the box?

2. Relevant equations

$$E_n=\frac{h^2n^2}{8mL^2}$$

3. The attempt at a solution

My question is, since E_n and n^2 are both on separate sides of the equation in the numerator, why can’t I put Delta in front of each of these variables and solve for L?

$$\Delta E_n=\frac{h^2\Delta n^2}{8mL^2}$$ and since the energy levels are adjacent, $$\Delta n^2=1$$

I tried doing this, but it gave me the incorrect answer. I know how I am supposed to do the problem now, I am just wondering why my original technique does not work.

Thanks,
Cooper

http://ift.tt/1mAs8ED


text:
# Quark-gluon vertex with an off-shell Oa-improved chiral fermion action

We perform a study the quark-gluon vertex function with a quenched Wilson gauge action and a variety of fermion actions. These include the domain wall fermion action with exponentially accurate chiral symmetry and the Wilson clover action both with the non-perturbatively improved clover coefficient as well as with a number of different values for this coefficient. We find that the domain wall vertex function behaves very well in the large momentum transfer region. The off-shell vertex function for the on-shell improved clover class of actions does not behave as well as the domain wall case and, surprisingly, shows only a weak dependence on the clover coefficient $c {SW}$ for all components of its Dirac decomposition and across all momenta. Including off-shell improvement rotations for the clover fields can make this action yield results consistent with those from the domain wall approach, as well as helping to determine the off-shell improved coefficient $c q^\prime$.

Author: Huey-Wen Lin

Source: https://archive.org/


text:
## FFT-based cosine similarity for fast template matching

A common task in computer vision applications is template matching, the search for a comparatively small image patch – or more likely, its closest approximation – in a larger image. In its simplest form, this implies solving the following optimization:

$$(i^*, j^*) = \arg \max_{i,j} s(T, P_{i,j}) \label{eq:tm}$$

Where the similarity metric $$s(T, P_{i,j})$$ is defined between a template $$T^{m_t \times n_t}$$ and all patches $$P^{m_t \times n_t}_{i,j}$$ such that:

$$P^{m_t \times n_t}_{i,j} = I[i:i+m_t,j:j+n_t] \label{eq:p}$$

For an image $$I^{m \times n}$$ with $$m_t \ll m$$ and $$n_t \ll n$$ (i.e. the image is much larger than the template). A common choice of similarity metric is cosine similarity, which is defined as:

$$cos(A, B) = \frac{A \cdot B}{\|A\| \|B\|} = \frac{\displaystyle\sum^{m,n}_{i,j} A[i,j]B[i,j]}{\sqrt{\displaystyle\sum^{m,n}_{i,j} A[i,j]^2 \displaystyle\sum^{m,n}_{i,j} B[i,j]^2}} \label{eq:cos}$$

Cosine similarity is a reliable metric, but as defined above its evaluation is rather costly. Combining formulas \eqref{eq:tm}, \eqref{eq:p} and \eqref{eq:cos} gives:

$$(i^*, j^*) = \arg \max_{i,j} \frac{\displaystyle\sum^{m_t,n_t}_{i_t,j_t} T[i_t,j_t] I[i + i_t, j + j_t]}{\sqrt{\displaystyle\sum^{m_t,n_t}_{i_t,j_t} T[i_t,j_t]^2 \displaystyle\sum^{m_t,n_t}_{i_t,j_t} I[i + i_t, j + j_t]^2}} \label{eq:tm_cos}$$

Which is of time complexity $$\mathrm{O}(m \, n \, m_tn_t)$$ – i.e. the size of the template times the size of the image. Depending on image and template sizes, the intended use case (e.g. batch vs. real-time) or scale of the template matching task (e.g. a couple dozen vs. thousands of images), this may incur in prohibitive processing costs.

Cosine similarity template matching can be sped up with application of the convolution theorem. First, let's redefine formula \eqref{eq:tm_cos} as:

$$(i^*, j^*) = \arg \max_{i,j} \frac{D_{T, I}[i,j]}{\sqrt{m_T M_I[i,j]}} \label{eq:tm_cos_2}$$

Where:

$$D_{T, I}[i,j] = \displaystyle\sum^{m_t,n_t}_{i_t,j_t} T[i_t,j_t] I[i + i_t, j + j_t] \label{eq:D_TI}$$
$$m_T = \displaystyle\sum^{m_t,n_t}_{i_t,j_t} T[i_t,j_t]^2 \label{eq:m_T}$$
$$M_I[i,j] = \displaystyle\sum^{m_t,n_t}_{i_t,j_t} I[i + i_t, j + j_t]^2 \label{eq:M_I}$$

Looking into the three terms above, it's clear that \eqref{eq:m_T} is constant for any given $$T$$ and can therefore be left out of the computation. On the other hand, \eqref{eq:D_TI} is just the cross-correlation between $$T$$ and $$I$$, which by the convolution theorem can also be computed as:

$$D_{T, I} = \mathcal{F}^{-1}(\mathcal{F}(T)^{*} \circ \mathcal{F}(I))$$

Where $$\mathcal{F}$$ is the fourier transform operator, $$\mathcal{F}^{-1}$$ the inverse transform, the asterisk denotes the complex conjugate, and $$\circ$$ is the Hadamard product (element-wise multiplication) of the two transforms. Likewise, \eqref{eq:M_I} can be computed as the cross-correlation between $$I^2$$ and a window filter $$W^{m_t \times n_t} = [w_{ij} = 1]$$:

$$M_I = \mathcal{F}^{-1}(\mathcal{F}(W)^{*} \circ \mathcal{F}(I^2))$$

The advantage of this approach is that algorithms such as the Fast Fourier Transform (FFT) are of time complexity $$\mathrm{O}(m \, n \, log \, m \, n)$$, which depending on the relative sizes of $$T$$ and $$I$$ may be faster than the $$\mathrm{O}(m \, n \, m_t n_t)$$ of the direct computation. Also the Fourier transforms of $$W$$ and (if the same template will be applied to several images) $$T$$ can be cached, further saving up computation time.

Implementation

The C++ code below provides a basic implementation of the method outlined above. It uses the popular OpenCV library, with some further optimizations particular to its implementation of the Fourier transform, explained in the comments.

#include <opencv2/opencv.hpp>

static const cv::Scalar ONE(1);

static const cv::Scalar ZERO(0);

static const cv::Scalar WHITE(255, 255, 255);

// Fourier transform performance is not a monotonic function of a vector
// size - matrices whose dimensions are powers of two are the fastest to
// process, and multiples of 2, 3 and 5 (for example, 300 = 5*5*3*2*2) are
// also processed quite efficiently. Therefore it makes sense to pad input
// data with zeros to get a bit larger matrix that can be transformed much
// faster than the original one.
cv::Size fit(const cv::Size &size)
{
return cv::Size(cv::getOptimalDFTSize(size.width),
cv::getOptimalDFTSize(size.height));
}

cv::Mat F_fwd(const cv::Mat &I, const cv::Size &size)
{
// Pad input matrix to given size.
cv::Mat P;
int m = size.height - I.rows;
int n = size.width - I.cols;
cv::copyMakeBorder(I, P, 0, m, 0, n, cv::BORDER_CONSTANT, ZERO);

// Compute Fourier transform for input data. The last argument
// informs the dft() function of how many non-zero rows are there,
// so it can handle the rest of the rows more efficiently and save
// some time.
cv::Mat F;
cv::dft(P, F, 0, I.rows);

return F;
}

cv::Mat F_inv(const cv::Mat &F, const cv::Size &size)
{
// Compute inverse Fourier transform for input data. The last
// argument informs the dft() function of how many non-zero
// rows are expected in the output, so it can handle the rest
// of the rows more efficiently and save some time.
cv::Mat I;
cv::dft(F, I, cv::DFT_INVERSE + cv::DFT_SCALE, size.height);

return I(cv::Rect(0, 0, size.width, size.height));
}

cv::Mat C(const cv::Mat &T, const cv::Mat &I, const cv::Size &size)
{
// Compute the Fourier transforms of template and image.
cv::Mat F_T = F_fwd(T, size);
cv::Mat F_I = F_fwd(I, size);

// Compute the cross correlation in the frequency domain.
cv::Mat F_TI;
cv::mulSpectrums(F_I, F_T, F_TI, 0, true);

// Compute the inverse Fourier transform of the cross-correlation,
// dismissing those rows and columns of the cross-correlation
// matrix that would require the template to "roll over" the image.
cv::Size clipped;
clipped.width = I.cols - T.cols;
clipped.height = I.rows - T.rows;
return F_inv(F_TI, clipped);
}

cv::Mat W(const cv::Mat &T)
{
return cv::Mat(T.size(), CV_64F, ONE);
}

cv::Point3f matchTemplate(const cv::Mat &T, const cv::Mat &I)
{
// Compute the optimal size for DFT computing.
cv::Size size = fit(I.size());

//Compute the cross-correlation and normalizing matrix.
cv::Mat C_TI = C(T, I, size);
cv::Mat M_I = C(W(T), I.mul(I), size);

int i_s, j_s;
float r = 0;
int rows = C_TI.rows;
int cols = C_TI.cols;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
float v = C_TI.at<double>(i, j) / sqrt(M_I.at<double>(i, j));
if (r < v)
{
r = v;
i_s = i;
j_s = j;
}
}
}

return cv::Point3f(j_s, i_s, r);
}

cv::Mat L(const cv::Mat &I)
{
cv::Mat L_I, L_F;
cv::cvtColor(I, L_I, CV_BGR2GRAY);
L_I.convertTo(L_F, CV_64F);
return L_F;
}

int main(int argc, char *argv[])
{


text:
# Length of root strings is at most 4

Let $\Phi$ be a root system. In his Introduction to Lie algebras and Representation Theory, J. Humphreys proves that if $$\beta-p\alpha,\dots,\beta,\dots,\beta+q\alpha$$ is the $\alpha$-root string through $\beta$, then $$\frac{2(\beta,\alpha)}{(\alpha,\alpha)}=p-q.$$ Then, he states that it follows "at once" that root strings are of length at most four.

I dont get why. Of course, we know that $-4\le 2(\beta,\alpha)/(\alpha,\alpha)\le 4$, but then length of the root string is $p+q+1$, not $p-q$...

-

By positive definiteness $0 \leq (\alpha, \beta)^2 < (\alpha, \alpha)( \beta, \beta )$ or, equivalently, $0 \leq (\alpha, \beta^\vee) (\beta, \alpha^\vee ) < 4$. Note the strict inequality.

Edit: I replaced $\langle \, , \, \rangle$ by $(\, , \,)$ to denote the inner product because of their conflicting interpretations.

-
What does $\beta^\vee$ mean ? Moreover, I don't see how/why this helps ? And by $\langle\alpha,\beta\rangle$, you mean $2(\alpha,\beta)/(\alpha,\alpha)$ ? –  Klaus Jan 7 '13 at 18:38
Thank you for the precision. However, I still don't understand why this gives $p+q+1\le 4$... Could you be more explicit ? –  Klaus Jan 7 '13 at 19:04
What $\alpha$-root string do you get for $\beta + q \alpha$ instead? What inequality can you derive in that case? –  WimC Jan 7 '13 at 19:15
Sorry, I must be very stupid today. I had this idea before, but the $\alpha$-root string for $\beta+q\alpha$ is $$\beta+q\alpha-(q+p)\alpha,\dots,\beta+q\alpha,\dots,\beta+q\alpha+0\alpha,$$ so we find $q+p=2(\beta,\alpha)/(\alpha,\alpha)+2q$, which we already knew... –  Klaus Jan 7 '13 at 19:30
Or in other words $q+p = (\beta + q\alpha, \alpha^\vee) \in \{0, 1, 2, 3 \}$. (Note that $\beta + q\alpha$ is itself a root.) –  WimC Jan 7 '13 at 19:36

\noindent I had trouble with exactly the same sentence in Humphrey's book (last sentence before the exercise on page 45 --- there was no \lq at once\rq\ for me). After googling, I ended up on this webpage, but I found the exchange of remarks tricky to follow. For the record, an easy way to prove that a root string has length at most 4 is to note that the sequence $$\langle \beta + i \alpha, \alpha \rangle, \enspace \hbox {where i is an integer},$$ forms an AP with difference 2. If $\phi$ and~$\psi$ are any two linearly independent roots, then $$\langle \psi, \phi \rangle =-3, -2, -1, 0, 1, 2 \hbox { or } 3,$$ from which it follows that the root string has length at most 4. \medskip

\noindent The formula $r - q = \langle \beta, \alpha \rangle$ becomes really useful slightly later when constructing the Hasse diagram of the positive roots from a base of simple roots using root strings: $$\hbox {string length} = r + q + 1 = 2r + 1 - \langle \beta, \alpha \rangle.$$ In particular, when $r=0$ (that is, when $\beta - \alpha$ is not a root, as happens when $\alpha$ and $\beta$ are simple roots), then the string length is $1 - \langle \beta, \alpha \rangle$.

-
The site is not entirely TeX... You don't need the \noindent's –  Arkamis Aug 2 '13 at 3:16


text:
SEARCH HOME
 Math Central Quandaries & Queries
 Question from Asha: {2x=-3y …1 {x-2+-4/3(y+1) ...2 note: … is equation

Hi,

I think there is a typo in your question. I think the first + in the second equation should be =. Let me know if I am mistaken.

If I am correct then the equations are

$2x = 3y \mbox{ and } x-2 = -\frac43 (y+1).$

The first task I would perform is to eliminate the fraction in the second equation. To do this multiply both sides of the second equation by 3 to get

$3\left(x-2\right) = 3\left(-\frac43 (y+1)\right)$

which then becomes

$3x - 6 = -4(y + 1).$

Simplify and then solve the simplified equation with the first equation. Make sure you verify your answer.

Write back if you need more assistance,
Harley

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.


text:
# 7

This grew out of an exchange with Jessica Taylor during MIRI’s recent visit to the FHI. Still getting my feel for the fixed point approach; let me know of any errors.

People at MIRI have recently proved you can use reflective oracles so that agents can use them to reason about other agents (including other agents with oracles) and themselves, and consistently reach Nash equilibriums. But can we do better than that?

To recap, a reflective oracle is a machine O such that:

• P(A()=1)>p implies O(A,p)=1

• P(A()=0)>1-p implies O(A,p)=0

This works even if A() includes a call to the oracle within its code. Now, all the algorithms used here will be clearly terminating, so we’ll have the other two implications as well (eg (P(A()=0)>p implies O(A,p)=0). And given any δ, we can, with order log(1/δ) questions, establish the probability of A() to within δ. Thus we will write O(A()==a)=p to mean that O(A()==a,(n-1)δ/2)=1 and O(A()==a,(n+1)δ/2)=0, where (n-1)δ/2 < p < (n+1)δ/2.

Note also that O can be used to output a probabilistic output (to within δ), so outputting specific mixed strategies is possible.

If p1 and p2 are two probability distributions/strategies over possible agent outputs, define them to be “δ-Pareto” if they are within δ of Pareto strategies. We can differentiate (p1,p2) for small changes in strategy, by infinitesimally increasing the weight of some pure strategies o1 and o2 (note that for each strategy, we actually have one less independent degree of freedom than the number of pure strategies, since probabilities must sum to 1). We’ll say D(p1,p2)(o1,o2) is Pareto if we are sure that it is an improvement for both players for all possible (p1’,p2’) within the respective δ ranges of (p1,p2).

If p1 and p2 are two probability distributions over possible agent outputs, we can consider

We’ll make the following two assumptions:

• The players do not make use of each other’s internal structures, just of the possible outputs and the calls to O().

• The players do not have access to a joint source of randomness.

So now fix 1 >> ε >> δ > 0, assume the problem is the Prisoner’s dilemma as given in the previous figure, let Q() be the other player, and consider the following algorithm:

define LP():
For all outputs o1 of LP(), compute O(LP()==o1).
Call the probability distribution generated p1.
For all outputs o2 of Q(), compute O(Q()==o2).
Call the probability distribution generated p2.
If exists o1 and o2 such that D(p1,p2)(o1,o2) is δ-Pareto:
-With probability 1-ε output p1.
-With probability ε output o1.
Else output p1.

Now, what does this algorithm do? To answer that, we need to consider its fixed points. Since ε >> δ, the only possible fixed points are those where the “With probability 1-ε…” output does not happen (even the degenerate case p1=o1 is not possible, as then D(p1,-)(o1,-)=0 since the probability of o1 cannot be further increased).

Thus (p1,p2) must be strategies such that there do not exist o1, o2 making D(p1,p2)(o1,o2) δ-Pareto. In the prisonner’s dilemma, there is always a possibility of Pareto improvement by increasing mutual cooperation (o1,o2)=(C,C), so p1 and p2 must themselves be δ-Pareto. Thus LP() will always reach δ-Pareto outcomes with Q(). The name LP stands for “locally Pareto” (we’ll revisit the “locally” later).

Though LP() achieves Pareto outcomes, this is not always ideal. If Q()==LP(), they will achieve some Pareto outcome, but it could be any. If Q() is the cooperation rock, then p1 could be any mix of defect and cooperate, as all those outcomes are Pareto. More worryingly, if Q() is the defection rock, LP() must cooperate (to within δ), as that is the only Pareto outcome.

To deal with this, consider neLP() (non-exploitable LP()). Define O(p1,p2) as the module computing the two probability distributions. The value of (p1,p2) is the expected utility of these according to the agent. If we say the value is δ-surely less than some other number, that means that value of (p1’,p2’) is strictly less than that number for all possible p1’ and p2’ within δ of p1 and p2, respectively.

define neLP():
O(p1,p2)
Let min be the minmax value, from strategy p1'.
If the value of (p1,p2) is δ-surely less than min:
-Output p1'.
If exists o1 and o2 such that D(p1,p2)(o1,o2) is δ-Pareto:
-With probability 1-ε output p1.
-With probability ε output o1.
Else output p1.

If multiple o1 exist, it chooses randomly among them.

For the prisoner’s dilemma, p1’=D and min=1. When playing against defection rock, p2 must be within δ of pure defection. The “If the value of…” clause prevents neLP() from cooperating with a probability larger than order δ. Therefore, neLP() will compute a (p1,p2) that, most of the time, will cause it to defect (“Output p1’”), and around δ/ε of the time, to go through the “If exists” loop, and cooperate with probability ε, resulting in cooperation of order δ.

What happens when neLP() plays itself? The two players must have either the same values for the probabilities in p1 and p2, or values that are δ/2 apart. The two “probability zones” computed by the two players must thus touch, at a corner is nothing else. The first player will think the outcomes are δ-surely less than min if its “zone” has value strictly less than 1; conversely for the second player. Thus the touching point must have coordinates (a,b) with a<1 and b<1 - but such a point does not exist in the prisoner’s dilemma outcome space.

So at least one player must reach the “If exists…” clause. But, as before, for the prisoner’s dilemma, strategies that trigger that clause are not stable. So the players must reach a δ-Pareto outcome. By the earlier conditions, this must be one that is not δ-less than (D,D) for either player. Consequently, it must be on the red boundary of the following figure:

The red boundary is what neLP() can achieve against copies of itself. The combined red and blue boundary is what neLP() can achieve against LP() and cooperation rock.

Can we do better? We might be tempted to increase “min”. If we increased min to 2, say, then surely the result would be Pareto in the “greater than 2” region? Have we successfully moved from “non-exploitable” to “exploits”?

However, though this works against LP() and cooperation rock, it runs into trouble when playing against itself, as “you both defect” becomes a possible oracle answer. A better solution is to define the “allowable region” as the green one here:

Thus the “If the value of…” line is replaced with “If the value of (p1,p2) is δ-surely not in the green zone” and the argument goes through as before. If such an agent faces a copy of itself, the combined allowable region is the kite delimited by the darker green lines, and then the outcome will be along the Pareto light green lines.

The “green” agent will even be able to cooperate with the “yellow” agent, the one whose allowable region is the yellow triangle. Since their allowable regions overlap, the outcome will be the Pareto segment at the top of the overlap.

However, two “yellow” agents will not be able to cooperate, and will mutually defect. By becoming too greedy, and insisting on a higher share of the prize, they’ve made mutual cooperation impossible. This seems to be a general trend: to make yourself better against some agents, you make yourself worse against others.

But the prisoner’s dilemma is an unusual kind of problem: the space of all possible expected outcomes can be reached by individual players choosing independent mixed strategies.

To see that this need not be the case, consider the variant of the PD where the rewards for defection are much larger:

The background grey triangle is the space of all possible expected outcomes. However, by choosing independently, the agents can only reach the purple area. All previous agents that reached a Pareto outcome - LP(), neLP(), Green-neLP() and Yellow-neLP() (apart from Yellow-neLP() against itself) - will still reach a “Pareto” outcome here, where Pareto means that it cannot be mutually improved without a joint source of randomness.

Now this PD variant is bad enough, but there are some problems where the “Pareto” boundary is very far from the ideal one. Consider this variant of the coordination problem:

Unless one player gets almost all their utility, the outcome is likely to be very suboptimal.

But things can be even worse than that. Consider the stag hunt problem:

Here there is also an area that can’t be reached, but since it’s Pareto-dominated by the area that can be reached, that isn’t the problem. The problem is that at the (Hare,Hare) equilibrium point at (3,3), there are no local Pareto improvements. Any increase in the probability of Stag, by either or both players, cannot increase the joint utilities.

The LP(), neLP() agents can therefore converge to (H,H) as an equilibrium.

Indeed, it’s only when one player has a probability of Stag greater than 3/4 (or both with probability greater than 3/8), that it becomes possible for there to be local Pareto improvements in the direction of (S,S). It’s perfectly possible to modify LP() into P() (no longer local) so that it increases S (and thus decreases its utility) if the probability of S is below 3/8.

If this happens, then two copies of P() will reach (S,S) on the stag problem. If P() is willing to increase the probability of S up to 3/4, then it will reach (S,S) against LP(). But that means that P() has laid itself open to ending up at a value of (3/4)0+(1/4)3 = 3/4 if it’s faced with a Hare-rock. Again, to make things better against some agents, one has to make things worse against others.

What if the agents has some joint source of randomness, say a process R() that takes certain values, which they will see before their final decisions? Assume that R() is δ2-complete, in that we can divide the set of outcomes from r into 1/δ2 disjoint sets, each with probability less than δ2 + δ5 (we use δ5 so that, even when summed over all δ2 sets, the error remains bounded by δ3).

Let p be a combined probability distribution over the two agents and R(). Given the fineness of R(), we can “ε-move” p towards any point on the true Pareto boundary, with resolution δ. To see that, let A=q(o1,o2)+(1-q)(o1’,o2’) be the target point on the Pareto boundary. Then choose randomly a set R1 of outcomes of R(), of probability εq, and a set R2 of probability ε(1-q). Replace p with p’, where p’=(o1,o2) on R1, p’=(o1’,o2’) on R2, and p’=p otherwise. This obviously ε-moves p-{R1,R2} towards A, and since R1 and R2 were chosen randomly, the whole process moves p towards A.

Then we can define the GP() (Globally-Pareto) agent:

define GP():
For all outputs o1,o2,r of (GP(),Q(),R()),
compute probabilities.
Call the probability distribution generated p.
If p is not δ-Pareto:
-ε-move p towards some point on the Pareto boundary.
-output the ε-moved p.
Else output p.

Of course, “output p” means output the GP() portion of p, and this choose randomly among points on the Pareto boundary.

This must reach a globally Pareto point, and, of course, there are also various neGP() variants.

New Comment