« first day (3330 days earlier)   

12:10 AM
Hello everyone, I'm new to the chat room and in full disclosure I'm working on homework for a graduate-level applied math course. I'm also pretty new to doing proofs.

What is the general strategy for proving that an algorithm is backward stable?

Here is the specific problem that I'm working on: https://imgur.com/0ja9taE
 
Full disclosure: We have more unapplied than applied math geeks in here, so you may not get help unless the right people are around.
 
Thanks @ted
 
In particular, I know some applied stuff but absolutely nothing about what you're thinking about.
 
Proofs in general are difficult for me, in my undergrad I really tried to avoid memorizing patterns vs building real understanding. Still feel like I'm unprepared for proofs, different type of thinking.
 
I believe your professor stated the problem very sloppily, which won't help. Have you taken a beginning real analysis course? This is of that same flavor.
I believe his statement should be something like: given any $x$ and $\varepsilon>0$, there is an $\tilde x$ so that blah blah blah.
In other words, the $\tilde x$ is going to depend on $\varepsilon$.
The $C$ is supposed to be universal.
 
12:19 AM
I haven't done any work in real analysis, unfortunately. How do you mean "universal" about $C$?
 
The flavor of this question makes me think some real analysis experience might be a good prerequisite. I mean the point is that the constant $C$ is supposed to work for all $x$ and all $\varepsilon$ and appropriate $\tilde x$.
 
In various branches of mathematics, a useful construction is often viewed as the “most efficient solution” to a certain problem. The definition of a universal property uses the language of category theory to make this notion precise and to study it abstractly. This article gives a general treatment of universal properties. To understand the concept, it is useful to study several examples first, of which there are many: all free objects, direct product and direct sum, free group, free lattice, Grothendieck group, Dedekind–MacNeille completion, product topology, Stone–Čech compactification, tensor...
 
Oh, and I didn't state what he did, the $\tilde x$ has to give you result of the algorithm when you plug it into $f$.
No, no, no, @Ryan, not helpful.
 
lol
it will be when some number theorist categorifies analysis
 
So the thing you need to analyze, @Joseph, is this: How well does taking the floor of the square of the floor of $x$ approximate $x^2$?
 
12:23 AM
That sounds interesting re real analysis, maybe I'll try to get some self-study in on real analysis. I see what you're saying about universality, yes, that makes sense.
 
So, if you choose $\tilde x$ with $\tilde x^2 = \text{alg}(x)$, can you estimate $|x-\tilde x|/|x|$?
I guess I don't understand this. You don't get much freedom in choosing $\tilde x$. It's essentially unique (up to sign), given $x$.
 
I hadn't thought of it in terms of a floor. I think that would assume a truncation rounding strategy. I'm gathering that IEEE typically has a different rounding strategy - en.wikipedia.org/wiki/IEEE_754#Rounding_rules
assuming truncation might be fair enough for this problem since it doesn't explicitly state.
 
But if you make $\varepsilon$ smaller, you have to be able to move $\tilde x$ closer to $x$. So I totally do not understand this.
Oh, what does fl mean?
floating?
 
floating point representation of the true value
yes,
 
Aha. My bad.
 
12:29 AM
np
 
Oh, I see, so fl depends on $\varepsilon$. Now it makes more sense.
I'm out of my league :)
 
the top problem here seems to be a similar problem: bicmr.pku.edu.cn/~dongbin/Teaching_files/UA575A.13f/…
 
So the point is that $x$ and $\text{fl}(x)$ differ by (at most) machine $\varepsilon$. You want to see what happens when you do the squaring stuff.
 
I believe $fl(x) = x(1+\delta)$, where $|\delta| < \macheps$.
yes, I hit enter before reading your last post
 
Is the error between fl($x$) and $x$ scaling with $|x|$ or is it absolute?
Oh, I guess what you wrote makes sense.
 
12:34 AM
I believe it would be absolute because it is basically just roundoff
 
No, I'm not worrying absolute value. I was worrying about whether the error should scale with $x$.
Anyhow, I think you know what to try to do now.
 
wouldn't the error be invariant to $x$ since it is based on roundoff?
yes, I think I'll get it
thanks for the help
 
Well, you put the $|x|$ multiplying $\delta$. I guess if you do a huge number, the roundoff error will be more significant, obviously, than if you do a small number. The computer can keep track of only so many significant digits. So I'm saying I think what you wrote makes sense to me.
 
ah, I see what you're saying
@TedShifrin, what is a good intro text for real analysis?
 
Hmm, here's a non-traditional suggestion, but a much more intuitive treatment, working only (for most of the book) on $\Bbb R$. Look at Arthur Mattuck's Introduction to analysis.
 
12:46 AM
Great! The amazon description looks like it was written for me - amazon.com/Introduction-Analysis-Arthur-Mattuck/dp/1484814118
 
I know the book reasonably well, and know the author extremely well.
 
There is also Yet Another Intro to Analysis
Victor Bryant.
It's pretty intro, though.
 
Mattuck's book is in the spirit of approximating within $\varepsilon$, which I think is exactly what @Joseph needs.
Mattuck wrote the book because so many students (not headed to PhD's in pure math) at MIT were failing the Rudin real analysis course.
 
Yeah I just like to suggest Bryant's book since I had not heard about it until I was in my masters.
 
I just picked up the Mattuck book for a good price (used), thanks @TedShifrin
 
12:49 AM
I was convinced that there does not exist a good book on analysis.
 
Wow, that was fast, @Joseph.
My book is an excellent book for multivariable analysis, @anakhro :)
 
Heh
 
If it is less than ten bucks and from a good recommendation.. don't need too long to make that decision.
:)
 
Oh, that is super cheap. I hope the book is usable.
 
I have been writing more lately. I wrote a little diddle on the non-squeezing theorem in symplectic topology aimed at students who only had a first course in linear algebra (which included vector spaces).
I approached it in the linear case so there was no need for Gromov or manifolds in the slightest.
Just a little 11pg pdf.
 
12:51 AM
Don't do as a grad student things that are better saved until you have tenure :P
 
yep, yep, I'm sure it is quite a bargain at that price
 
Why is it better to write when you are tenure?
I find writing about things is one of the best ways I know to grok things.
 
Because now you need to be concentrating on your career, research publications.
 
I am more concerned with pedagogy than research, unfortunately.
 
I mean ... obviously I have always cared more about teaching and explaining than the average bear.
Well, I cannot fault you for that, but in today's world it may cause you career problems.
 
12:53 AM
Yeah, I am not sure how long I will stick with academia.
Already have too negative of an opinion on academia to cut it.
Also I probably am not cut out for it.
 
Well, I'm not gonna try to twist your arm. I would not have made it in today's world.
 
Because you were average back then, having Chern as your advisor and all. ;)
 
No, obviously, I had more than my share of advantages.
 
How did you first get in contact with Chern? Was it by chance?
How did you get into geometry?
 
But academia has changed to being more research money oriented, far more slave labor being hired rather than hiring tenure-track faculty.
Well, he was one of my qualifying exam examiners (in algebra, ironically). But, actually, we had met when I was 7, and he actually remembered when I told him.
So that was quite a laugh.
 
12:57 AM
At 7? Did you have family who were mathematically inclined?
 
(I grew up in Berkeley. My dad was a music prof. We rented an apartment in Paris for 3 months when I was 7, as it turns out, from a famous mathematician who was going to spend the year in Berkeley at our house. Chern and his family were moving out of the Paris apartment as we moved in.)
 
Wow, coincidental.
 
Yeah, pretty funny. So a lot of Berkeley's math department, it turns out, had been in my childhood house.
I truly doubt this is why Chern agreed to be my adviser, however :)
 
Heh. Yeah I wouldn't think so.
Were you always interested in math throughout school?
 
@TedShifrin the distinction between "full time" and "tenure-track" is huge
 
12:59 AM
And he was actually very supportive of my caring about teaching. Of course, he got to let me cover his classes whenever he was traveling.
@Semiclassic: I am fully aware.
 
yeah, bit of an obvious statement
or, at least, obvious for anyone in academia.
 
Well, lots of people in here wouldn't have a clue about it, Semiclassic.
 
Sort of a fear in the back of my mind I won't make it through my Ph.D.
I feel like I have too much to catch up on.
 
Well, you can't learn/know everything.
 
1:02 AM
I am told "imposter syndrome" is rampant, though. It's hard to convince yourself you are insane, though.
 
I'm just reading a review of Bryant's book. Looks like it doesn't even get to things like pointwise and uniform convergence. That's a liability.
 
@TedShifrin yes it is extremely introductory.
It's like intermediate between calc and analysis.
It is mostly motivational.
 
I'll stand by my recommendation.
For applied math, it's really important to understand things like uniform convergence.
 
I usually suggest it to those who are having troubles grasping the point behind analysis, or those who want to "get ahead" but don't want to spoil the class they will be taking in the next year.
It's really good as a supplementary book.
 
Yeah, my fondest recommendation is Spivak's Calculus, but it's totally serious.
 
1:06 AM
Spivak at least has excellent exercises.
 
So did you ever put the finishing touch on our discussion of the normal bundle of $K$?
Superb exercises.
Of course, I say that having written hundreds of them :P
 
The ToC of Bryant's book in case it wasn't online
You can tell from this that he doesn't actually cover much in detail.
I haven't had a chance to write out the details, but I think it will iron out. Just need to make time to do it.
 
OK, I'll shaddup.
 
@TedShifrin it's not because of you talking to me, but I am working on some other more pressing things. Paper work, an assignment, and the finishing edits on my thesis before I submit it for my degree.
 
Not to mention wasting so much time in here.
Finishing edits in September?
When do you graduate?
 
1:16 AM
I only defended at the end of August. I technically have my degree in the bag already, it's just a matter of doing the edits that the examiners suggested.
Which were not that many...I just have put it off because I started my Ph.D.
 
Oh wow. Almost congratulations.
Ohhhhh ... you mean MA thesis. I thought you meant the ultimate.
 
No, not Ph.D.
 
Got it. I'm no longer confuzled.
 
Yeah. But new city, new university. They also even have geometry courses at this university. ;)
My alma mater didn't have any geometers.
 
Aha. I see. That makes more sense.
 
1:19 AM
Though I am a bit disappointed because the geometry course I have to take for the comprehensive is just G&P's differential topology book. :/
 
Hmm, what about Riemannian geometry, etc.? Post comprehensive.
Well, good thing we were just discussing G&P.
 
They have a Riemannian geometry course, yeah. And they have tonnes of symplectic geometers. So I am in good company.
 
Cool.
 
And yeah, it was good reminder of Whitney's proof.
But I am going to have to step it up. Little gaps in my intuition and knowledge where I just fail to see little things like you point out. I feel like they should be more obvious but I am just lost sometimes.
 
So have you talked to any of the symplectic folks about giving you a problem?
 
1:21 AM
Not yet, I was going to get on that because there are applications due for research proposals for external funding.
 
Well, in fairness, I taught G&P about 6 times or more in my career.
And graduate manifolds/diff geo another 4 or 5 times.
 
Any good questions today? Yesterday?
 
Since I have mostly just focused on 3D contact geometry, I am unsure about what I would actually want to do. But I will definitely ask around.
 
No, @MikeM, only tomorrow.
 
Hi Mike.
 
1:23 AM
OK. See you then.
 
Mike really likes to expedite his internet usage.
I hope he's doing well.
@TedShifrin are Ph.D. problems usually given to you, or are they usually more open ended?
Because my M.Sc. problem was given to me, so I thought maybe the next step up was more independent, but maybe that's not the case. I certainly would have no idea where to start.
 
Hey, could someone help me with this problem: math.stackexchange.com/questions/3339422/…
 
Bob
where does this problem come from?
 
@QuoteDave is there a reason why you require the method to revolve around integration?
Some rhetoric, in an interval around a root, the only defining feature of the integral here is that the integral becomes small. However, the integral being small can happen in other scenarios where a root is not necessary.
So it would have to be more elaborate of a method than naively using integrals to refine to subintervals.
In spirit of Bob's answer, Newton's method uses differentiation (the opposite of integration) to find roots.
 
1:39 AM
about the only method I know about where integration is used for root-finding is in the context of complex contour integration and the argument principle
 
Bob
I am starting to think that by looking at some integrals you can get a good idea where the root(s) are and find them. However, it does not seem like the easy way to do it.
could somebody look at my question: math.stackexchange.com/questions/3357982/…
 
@Bob WA gives 7/12 for E(x), so I'd redo that computation
 
Bob
what is WA?
 
note that the antiderivative of xy is xy^2/2, not x^2 y^2/2
wolfram alpha
once you fix that, the integral should work out fine
 
Bob
@Semiclassical Please post that as an answer so I can give you some points and close the question.
 
1:51 AM
nah. feel free to post that yourself tho as an answer to your own question
 
Bob
@Semiclassical thank you and good night
 
Hi
 
2:07 AM
The beloved @usukidoll
 
2:18 AM
@MatheinBoulomenos hey
yesterday, by Leaky Nun
@MatheinBoulomenos can we characterize all additive functions from f.g. A-mod to N?
 
@LeakyNun hi
what is $A$? what is $N$?
 
$\Bbb N$
$A$ is say a noetherian ring
working conjecture: any additive function is a constant multiple of the dimension of tensoring with A/m where m is a maximal ideal
wait that isn't necessarily additive right
tensoring is only right exact
 
oh you mean the monoid of all f.g. A-modules?
 
I guess
$\lambda$ is additive if whenever $0 \to M' \to M \to M'' \to 0$ we have $\lambda(M') + \lambda(M'') = \lambda(M)$
see this already fails with "rank" with $A=\Bbb Z$
is the rank of $M$ the same as $\dim (M \otimes \Bbb Q)$
how does this work, $\Bbb Q$ isn't flat right
 
$\Bbb Q$ is flat ...
 
2:24 AM
oh no
 
but $\Bbb F_p$ isn't flat over $\Bbb Z$
flat = torsion free over a Dedekind domain (or more generally Prüfer domain)
 
do we have other additive functions
I think if $A$ is a field then my conjecture is trivial
 
there are no other functions for $A$ a PID.
Proof: Over a PID submodules of free modules are free, so every module has a free resolution of length two. It follows that an additive function on f.g. modules is uniquely determined by $\lambda(A)$
 
but is your resolution a finite presentation
 
As $0 \to A^n \to A^m \to M \to 0$ implies $\lambda(M)=(m-n) \lambda(A)$
 
2:30 AM
oh right
 
@LeakyNun yes, but it's stronger than that, a resolution is exact on the left
 
there's the STFGMPID
cool
 
submodules of free modules are free is weaker than STFGMPID, it's used in the proof
at least the proof I know
 
but I'm talking about whether every $M$ has a f.p. resolution
oh right
 
what do you mean?
 
2:31 AM
never mind
 
every f.g. module over a PID has a resolution of length two by free modules of finite rank
sorry if I was unclear
 
what are you doing in this hour of the day
 
being drunk, coming home from a party and being unable to sleep
 
drunk maths is the best maths
so more generally if $A$ is a DD.... something something valuation
oh I saw a proof that ideals in DD have unique prime factorization
and like wow it's so much more beautiful than the proof I usually see
with Noetherian induction and whatnot
 
If you have the thing that every f.g. module admits a resolution of the form $0 \to A^n \to A^m \to M \to 0$ than the proof of STFGMPID is just write down a Smith Normal form of the map $A^n \to A^m$
 
2:34 AM
every ideal is contained in product of primes
and then some steps I forgot
 
you can use the sledgehammer approach and refer to primary decomposition if you want
 
lol
 
a Dedekind domain is locally a discrete valuation ring and for a $\mathfrak{p}$-primary ideal, being a power of $\mathfrak{p}$ behaves well under localization. For powers of comaximal ideals, intersection is the same as product QED
where QED means the rest is primary decomposition
 
I'm going to hell in one of my proofs :(
 
2:49 AM
A space is hausdorff if for any two distinct points there exists a neighborhood of each which are disjoint from eachother. If we have a trivial topological space like the empty set - since there aren't any two distinct points - is the space hausdorff by default?
I am leaning toward yes since the definition for hausdorff is in the form of if p then q so if not p then the truth table is always true.
 
@LeakyNun if $A$ is Dedekind, your conjecture holds, but the argument I can think of is more difficult.
by STFGMDD every f.g. torsion module over a Dedekind domain is a direct sum of cyclic torsion modules. for a cyclic torsion modue $A/(a)$, we have a SES $0 \to A \to A \to A/(a) \to 0$ which implies $\lambda(A)=\lambda(A)+\lambda(A/(a))$, so $\lambda(A/(a))=0$ and thus $\lambda$ vanishes on all f.g. torsion modules.
By STFGMDD, every f.g. module over a Dedekind domain is a direct sum of a free module, a fractional ideal and a torsion module. Let $I$ be a fractional ideal, then wlog $I \su
 
@MatheinBoulomenos see I knew you're the right person to ask :P
 
Like I should be using transductive induction for if \alpha \leq \beta$ then $\alpha \gamma \leq \beta \gamma$. What I got so far is for the zero case just let $\gamma = 0$. XC
Ordinal multiplication nyaaaa ~~~
 
rip latex
 
Oh crud
Anywayyyyy I'm stuck :C
Successor case would be let some symbol be another symbol + 1 and I should get those inequalities
$ \gamma = \zeta +1$
I wonder if someone else asked this already :/
 
3:04 AM
@LeakyNun if $e$ is a central idempotent, then the monoid of f.g. $A$-modules (usually denoted A-mod with small m as opposed to A-Mod) is the direct sum of $A/(e)$-mod and $A/(1-e)$-mod, so wlog $A$ doesn't admit nontrivial central idempotents. By Artin-Wedderburn and the Morita-invariance of the problem, we can classify additive functions on A-mod for A semisimple
I'm not sure I can do anything better than Dedekind domain/semisimple
 
semisimple = finitely many maximal ideals?
 
that's semilocal
there are a couple of equivalent definitions of semisimple
a semisimple module is a direct sum of simple modules
 
but what is a semisimple ring?
 
where simple = irreducible = no other submodues other than itself
a ring is semisimple if it is semisimple as a module over itself (left or right that's actually equivalent here)
 
so seimsimple => semilocal?
 
3:07 AM
yes
 
semisimple = semilocal + zero jacobson radical?
 
the correct "noncommutative definition" of semilocal is actually that $A/J(A)$ is semisimple
so yes
finitely many maximal ideals is only equivalent to that in the commutative case
 
is J(A) a both-sided ideal?
 
what is J(A)?
 
3:08 AM
intersection of all left maximal ideals
= intersection of all right maximal ideals
 
woah
 
= intersection of all annihilators of all left (or equivalently right) simple modules
 
how on earth
 
I don't recall the proofs off the top of my head
it's all in Lam
 
cool
@MatheinBoulomenos given an $n$-dimensional projective variety $C$
what's the smallest $m$ such that we have an embedding $C \to \Bbb P^m$?
 
3:16 AM
@LeakyNun no idea
@LeakyNun
Lemma: let $\lambda$ be an additive function on $A$-mod, then for an exact sequence $0 \to M_1 \to M_2 \to \dots \to M_n \to 0$, we have $\sum_{k=1}^n (-1)^k M_k = 0$.
Proof: Use induction and split the SES into a shorter SES
Proposition: Let $A$ be a regular local ring, then any additive function $A$-mod $\to \Bbb N$ is a constant multiple of $M \mapsto \mathrm{dim}_K K \otimes_A M$ where $K$ is the quotient field of $A$ (regular local rings are domains)
Proof: By a result due to Serre, regular local rings have finite projective dimension. By a result due to Kaplansky, projective
 
wow
 
3:49 AM
@AkivaWeinberger hi
 
loud startled noises
yes hi
 
so you know how combination with repetition is (n+r-1) choose (r-1) right
 
Not n^r?
What do you mean by combination with repetition
 
so multisets essentially
count the number of length-r multisets whose elements are selected from {1, .., n}
 
Oh OK right
not counting order
Right yeah sure
Stars 'n' bars and all that jazz
 
3:52 AM
it turns out that the quantity is equal to (-1)^n ((-r) choose n) and i'm wondering whether there's a combinatorial proof
 
Hm
Well
$(1+x)^{-r}$
if you do binomial expansion to it
you get $\sum\binom{-r}nx^n$ I think?
but also if you expand it as $(1-x+x^2-x^3+\dotsb)^r$ first
then look at the coefficient of $n$
you should hopefully get the combination without repetition thing I dunno I haven't thought this through
 
hmm
 
'cause you're choosing how many of each of r objects you want
Yeah that works
I mean I dunno if generating functions are sufficiently "combinatorial"
but I dunno how to interpret $\binom{-r}n$ combinatorially
 
me neither
 
So 3Blue1Brown is like a day or two away from crossing 2^21 subscribers
which means we should expect another Q&A soon
 
4:03 AM
@LeakyNun let $A=k[x_1,\dots,x_n]$. Then $A$ has finite projective dimension as $A$ is regular (due to Serre). By the Quillen-Suslin theorem, f.g. projective modules over $A$ are free. Thus any f.g. module over $A$ admits a finite resolution of free modules of finite rank. Now do the same argument as in the last proof, showing that an additive function $\lambda:A\text{-mod} \to \Bbb N$ is uniquely determined by $\lambda(A)$, thus $\lambda$ is a constant multiple of the rank function
 
nice
 
4:31 AM
hi @Ted
 
5:09 AM
Ghost function:
f(f(x))=y, but (ff)(x)=x and f(x)=x
order matters
 
5:33 AM
Having some trouble with combinatorics
 
 
3 hours later…
8:05 AM
I want a book that discusses basics of computer programming
by basic i mean following topics should be covered
Arithmetic and logical operations on numbers;
Octal and Hexadecimal systems;
Conversion to and from decimal systems;
Algebra of binary numbers.
Basic logic gates and truth tables,
Boolean algebra, normal forms.
Representation of unsigned integers, signed integers and reals, double precision reals and long integers.
Algorithms and flow charts for solving numerical analysis problems.
 
8:27 AM
Id(x+x)
Id(x)+Id(x)=x+x
identity function thus is always linear
 
8:51 AM
Hello math folks
@Secret Remember your $'s
 
9:24 AM
$$
\begin{array}{l}{\text { (a) }\left\{\frac{n}{n+1} : n \in \mathbb{N}\right\}} \\ {\text { (b) }\{r \in \mathbb{Q} : 3 \leq r<5\}}\end{array}
$$
Find interior boundry complement and closure of this set
 
9:41 AM
o/ Question: What is the "height" of a flag manifold/variety $G/P$?
 
@Danu five foot three
 
0 out of 10
 
Well I tried
 
@Danu Do you want to say what that means so the rest of the class can follow along?
 
10:01 AM
A flag manifold is a homogeneous space of the form $G/P$ with $G$ a complex Lie group and $P$ a parabolic subgroup. That's not how I think about them, I was just hoping people'd be more familiar with it. The way I think about them is $G/C(T)$ where $G$ is a compact Lie group (compact real form of the above $G$) and $C(T)$ the centralizer of a torus (any torus!) in $G$.
The height is supposed to be some Lie-algebraic thing I think
 
that was the part i needed explained
 
I'm probably failing to provide some other crucial information but I can't tell
 
you misread me. I do not know what the height is.
the height is the part I need explained
 
oh
well, I also have no clue
 
nobody here will know better than you...
 
10:07 AM
RIP
 
For all you know five foot three was the answer
and you yelled at me for nothing
 
 
1 hour later…
11:35 AM
What does one mean by norm decreasing?
For an operator
 
12:30 PM
@SayanChattopadhyay what's the full sentence?
It might mean that $\|A(x)\| < \|x\|$ for an operator or something like that.
Or the distance function is decreasing
Like $d(Ax,Ay) < d(x,y)$, where $d(a,b) = \|b-a\|$
 
12:52 PM
@anakhro Well, my function is easily integratable and no other methods work.
@Semiclassical Can you tell me more about complex integration? I heard about it before, and it seems promising, but the user failed to tell me more about how to implement it (preferably on Python 3.x)
 

« first day (3330 days earlier)