From stevenj.mit at gmail.com Wed Sep 3 19:43:28 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Wed, 3 Sep 2008 19:43:28 -0400 Subject: [18335fall08] Welcome to 18.335 Message-ID: <62B1BB6E-5D20-4670-8044-EBD372D3F960@gmail.com> Hello gang, I forgot to put the URL up on the board until some of you asked me about it after class, but the home page for the course this term is: http://www-math.mit.edu/~stevenj/18.335/ The handout today was just a printout of this web page, which lists the basic information about the syllabus, grading, textbook, etcetera. On the web site, after each lecture I will add a brief summary of what was covered, along with pointers to relevant readings in the text or elsewhere and links to any handouts. (Today's lecture summary will be up shortly.) As I mentioned in the beginning of today's class, as far as the numerical-linear-algebra content of the course we will be closely following the textbook in most cases (with a few exceptions, e.g. the text does not discuss memory efficiency). However, we will not be covering the material in the same order. Today's material on Gaussian elimination starts in chapter 20 of the book, and from there we will work backwards to build up the tools that we need to analyze error characteristics and to branch out to other algorithms. I will not review basic linear algebra except in the most cursor way; if you feel you need a refresher, I strongly recommend reading the first three chapters of the text (about 20 pages) by Friday. The first five chapters of the book are available for free online if you have not purchased the text yet; http://web.comlab.ox.ac.uk/people/Nick.Trefethen/text.html I highly recommend purchasing the text, which has become a classic in the field. --SGJ -------------- next part -------------- An HTML attachment was scrubbed... URL: http://mailman.mit.edu/pipermail/18335fall08/attachments/20080903/4dc87199/attachment.htm From stevenj.mit at gmail.com Mon Sep 8 21:44:33 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Mon, 8 Sep 2008 21:44:33 -0400 Subject: [18335fall08] 18.335 - problem set guidelines Message-ID: <39B4EBE4-CE60-4B97-84B7-47D51A1E7A9B@fftw.org> Hi gang, Problem set 1 was handed out today in class, and is also available on the web site (where all handouts are posted, along with lecture summaries): http://math.mit.edu/~stevenj/18.335 Just a few guidelines regarding due dates etcetera: First, in general late homeworks will not be accepted; you should turn it in during the scheduled class time. If something serious prevents you from turning it in on time, should should contact me 24 hours in advance for permission. I'm especially unsympathetic to emails sent at 3am the night before a pset is due. I would strongly encourage you to at least start on psets well before the due date. Regarding collaboration, I encourage you to talk to one another if you like (although I would recommend working alone on each problem for a while before discussing or googling it), and to read anything and everything you want, including other books, papers, etcetera. However, when it comes time to write up your solutions, I expect you to do so starting with a blank sheet of paper, with no solution (whether from another student or from a paper) sitting next to you to refer to. --SGJ From stevenj.mit at gmail.com Thu Sep 11 11:46:49 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Thu, 11 Sep 2008 11:46:49 -0400 Subject: [18335fall08] 18.335 pset1 correction to problem 2 Message-ID: <7C12EED4-5F43-4258-93D6-04098FBD543D@fftw.org> Hi gang, It turns out that I mis-stated problem 2 in a way that made it impossible (I think)---basically, your new "LU" factorization by the procedure I suggested would have an upper-triangular U, but not a lower-triangular L. I've posted a modified pset1 that corrects this by relaxing the problem somewhat. Please download and use the corrected pset1, posted on the 18.335 web page (math.mit.edu/~stevenj/18.335/pset1.pdf) --SGJ From stevenj.mit at gmail.com Sat Sep 13 16:16:25 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Sat, 13 Sep 2008 16:16:25 -0400 Subject: [18335fall08] disabling multiprocessing in Matlab for problem 3 Message-ID: <75E42D9D-E93F-4C99-829C-B54FC9D55FE7@gmail.com> Hi gang, One of you brought to my attention that Matlab may automatically parallelize its matrix-multiply routine if you have a multi-core machine (which most people do nowadays). This may lead to distorted or confusing results in problem 3 of the pset. You can turn off multiprocessing in Matlab by using the maxNumCompThreads function. In particular, doing maxNumCompThreads(1) should tell Matlab to use at most one processor. (Note that you have to do this each time you run Matlab, as when you launch it automatically uses all available processors by default.) (Other odd things can happen during benchmarking too. A colleague of mine recently pointed out some very weird behavior that can occur on laptops, especially under Windows, due to thermal management -- when the processor runs at full speed, it gets too hot and the system automatically slows it down. So, if you get weird inconsistent results on a laptop, you might want to switch to a desktop, as desktop machines are usually better cooled.) --SGJ From stevenj.mit at gmail.com Mon Sep 15 18:23:01 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Mon, 15 Sep 2008 18:23:01 -0400 Subject: [18335fall08] pset1 problem 2 clarifications Message-ID: Hi gang, A couple of more clarifications in problem 2. In part (f), in order to calculate K you have to know what N is. You can either compute K in as a function in terms of N, or, if you want, assume that the initial N was given by N=m(m-1)/2 (what you would get from ordinary gaussian elimination). In part (g), the "N" does not have anything to do with the "N" in the introduction; this was my mistake -- I forgot that I already had a variable named "N". I've posted a revised problem in which (g) uses "M" for the number of rank-1 updates. As in part (f), you can either phrase your answer in (g) as a function of N or you can assume N=m(m-1)/2. I've posted a revised PDF with these corrections. --SGJ From stevenj.mit at gmail.com Thu Sep 25 18:55:19 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Thu, 25 Sep 2008 18:55:19 -0400 Subject: [18335fall08] 18.335 pset 2 clarification Message-ID: <2D76035F-AAC6-48AA-8970-C22A42679F25@fftw.org> In problem 2, you should assume that the initial inputs x_i are floating-point numbers (i.e. they are in the subset of the reals that is exactly represented). --SGJ From stevenj.mit at gmail.com Sun Sep 28 01:32:49 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Sun, 28 Sep 2008 01:32:49 -0400 Subject: [18335fall08] pset2 erratum Message-ID: <0551E095-D92F-4AC5-87CD-5B8B44B265EE@fftw.org> Hi gang, On problem 2(b), it should be (n-i+1) rather than (n-i). --SGJ From stevenj.mit at gmail.com Sun Sep 28 18:38:11 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Sun, 28 Sep 2008 18:38:11 -0400 Subject: [18335fall08] Fwd: pset2 erratum References: <48DFDC9C.8070206@mit.edu> Message-ID: <733B1565-755B-4D0F-8CFE-83599669EDEE@gmail.com> One of you also pointed out the following correction: Begin forwarded message: > Would I be correct in assuming that the preamble to Problem 2 should > also have > > $\tilde{f}(x) = \tilde{s}_n$ > and > $\tilde{s}_k = \tilde{s}_{k-1} \oplus x_k$ > > instead of what's written there? From stevenj.mit at gmail.com Thu Oct 2 14:48:56 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Thu, 2 Oct 2008 14:48:56 -0400 Subject: [18335fall08] pset 3 correction Message-ID: <1B5818DE-2378-4D2E-9E67-58436F0BFC5E@gmail.com> In the equation for problem 1, I left out a couple of factors of A; the corrected version is now posted. --SGJ From stevenj.mit at gmail.com Thu Oct 9 16:06:46 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Thu, 9 Oct 2008 16:06:46 -0400 Subject: [18335fall08] matlab notes on problem 3 Message-ID: <954340FA-BBAF-49B1-874F-ECAFBA97CCDB@gmail.com> When you are reading an image into Matlab with "imread", it reads it in as an integer array, and you may have noticed that this gives an error with SVD etc. To perform an SVD, you need to convert this to floating-point. You can do this with the "double" command, e.g.: A = double(imread('myfile.jpg')); To plot it with pcolor, I noticed that pcolor displays it upside- down. Also, the grid lines are annoying, and the aspect ratio is distorted. You can plot it nicely with: pcolor(flipud(A)); colormap(gray); shading interp; axis equal Finally, I should mention that things are more complicated for a color image, which is why I recommend sticking to a grayscale image. For a color image, it reads it in as a three-dimensional array where the third dimension (for an RGB image) is red, green, blue. To convert a slice of this, e.g. A(:,:,1) into a 2d array for SVD, you would need to use the "squeeze" command: squeeze(A(:,:,1)). Then, I suppose you could do SVD compression on each color component individually, then combine them back together and write it out to a color file ..... but it is much easier to just use a grayscale image. Steven From stevenj.mit at gmail.com Thu Oct 16 00:17:01 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Thu, 16 Oct 2008 00:17:01 -0400 Subject: [18335fall08] pset 4 posted Message-ID: Hi gang, In case any of you didn't pick it up in class last Friday, pset 4 is posted on the web page (along with the pset 3 solutions). (Note that there was a typo in problem 2b: the approximate derivative p'(z) was missing an obvious factor of 2 in the denominator, which is corrected in the posted version.) Steven From stevenj.mit at gmail.com Wed Oct 22 19:54:51 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Wed, 22 Oct 2008 19:54:51 -0400 Subject: [18335fall08] pset4 solutions, pset 5, readings, mid-term exam Message-ID: <6DC19D77-EE06-4B4A-B195-B3B7D782B51D@fftw.org> Hi gang, I've updated the web site (http://math.mit.edu/~stevenj/18.335/). The solutions for problem set 4 are posted. Also, in case you weren't here on Monday, be sure to note that problem set 5 is posted and is due in one week. I've also posted some readings related to the recent lectures. For example, the approach to conjugate-gradient that I'm using is somewhat different from the one in the text (although the end result is the same), and is closer to one described in a well-known essay by J. R. Shewchuk that I've linked. For the remainder of the term, I plan on giving somewhat shorter problem sets -- enough to make sure you are thinking about the lecture materials, but giving you more time to work on your final projects (1/3 of your grade). Note also that the mid-term exam is coming up in two weeks, on Wednesday Nov. 5. What I am planning to do for the mid-term is to give you two hours, closed book, but you are allowed to bring in one sheet of paper covered with whatever notes you want. The problems from Trefethen are probably good practice, although of course we covered a few things like cache models that are not in the book. Anything covered in class through next Wed. (Oct 29) is fair game for the exam. Regarding the exam scheduling, my current plan is to reserve some room from 2-5pm. Then you can either take the exam from 2-4pm or from 3-5 pm. Please let me know if you CANNOT make one of these two slots. --SGJ From stevenj.mit at gmail.com Thu Oct 23 15:58:56 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Thu, 23 Oct 2008 15:58:56 -0400 Subject: [18335fall08] sample Matlab files for pset 5 Message-ID: Hi gang, To help you a bit with your Matlab coding, I've posted sample Matlab files for problems 2 and 3 that implement the matrices specified in those problems and also (unrestarted) Lanczos and steepest-descent (from lecture). Look at the lecture 18 entry on: http://math.mit.edu/~stevenj/18.335/ ---SGJ From stevenj.mit at gmail.com Sat Nov 1 17:56:16 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Sat, 1 Nov 2008 17:56:16 -0400 Subject: [18335fall08] pset5 solutions Message-ID: <6414E50F-A4B3-49AF-81D2-7924A59DAA18@fftw.org> Hi gang, the pset 5 solutions are posted at: http://math.mit.edu/~stevenj/18.335/pset5sol.pdf --SGJ From stevenj.mit at gmail.com Mon Nov 3 20:13:49 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Mon, 3 Nov 2008 20:13:49 -0500 Subject: [18335fall08] mid-term location, pset averages, etc. Message-ID: <2E9C6C24-5351-4154-9307-051FD50FA821@fftw.org> Hi gang, The mid-term on Wednesday will be in room 3-343. You can come EITHER from 2-4pm OR from 3-5pm. One page of notes is allowed. I'll also post a note on the door of our regular classroom (4-231) with the location on Wednesday. (I don't expect you to memorize extensive formulas; e.g. if a problem asks you about the Arnoldi algorithm or CG, I'll give you the algorithm. However, you should definitely know basic short things like what is backwards stability or what is the Schur decomposition.) The averages on the problem sets so far are: pset #1: 54.2/75 = 72.3% pset #2: 79.7/113 = 70.5% pset #3: 67.2/90 = 74.7% pset #4: 82.2/105 = 78.3% pset #5: 57/75 = 76% All psets will have equal weight in the final grade. If you are averaging in the mid 80%s or higher you are in pretty good (A-ish) shape. If you are averaging in the 70%s or high 60%s you are in B-ish shape. But of course, psets are only 1/3 of the grade, and I can't be sure of anything until I see the mid-terms and the final projects. I'll have office hours on Tuesday from 4:30-5:30pm. --SGJ PS. Your final projects look good, for the most part. If I have specific concerns I will email you. From stevenj.mit at gmail.com Mon Nov 3 20:55:52 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Mon, 3 Nov 2008 20:55:52 -0500 Subject: [18335fall08] pset5 grades Message-ID: Hi gang, It turns out that the TA misunderstood problem 3 and may have mis- graded it for some of you. In particular, he misunderstood what was meant by "restarted Lanczos". So, if you have a few points taken off because you "used the wrong algorithm" and it is unclear why, let me know after class or during office hours and I'll see if you should get a few more points. --SGJ From stevenj.mit at gmail.com Tue Nov 4 13:25:05 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Tue, 4 Nov 2008 13:25:05 -0500 Subject: [18335fall08] exam problems from previous terms Message-ID: Hi gang, I looked through the 18.335 exams from previous terms. Some of the problems are ones that I wouldn't be inclined to ask. The ones that are closest to things I might ask are: Fall 2005: problem 2, 3, 7, & problem 8 (but I would give you the eigenvalues -2, 3, 2, 1 in part a). Fall 2006: problem 5, 6, 7 See: http://ocw.mit.edu/OcwWeb/Mathematics/18-335JFall-2006/Exams/index.htm Note, however, that in previous terms the midterm did not cover exactly the same material. e.g. they had nothing on caches, and iterative algorithms (not including QR) weren't covered until after their mid-term. Here, caches and iterative algorithms are fair game. From stevenj.mit at gmail.com Wed Nov 5 16:58:57 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Wed, 5 Nov 2008 16:58:57 -0500 Subject: [18335fall08] mid-term exam & solutions Message-ID: <91E8E6D0-C1D6-4FD6-BBDA-73B658350AED@fftw.org> Hi gang, the exam and solutions are posted on the course web page. From looking at the first batch of your exams, it looks like I may have made the exam a little too tricky (or too long?). Don't worry; that just means it is likely to be heavily curved. --SGJ From stevenj.mit at gmail.com Thu Nov 6 18:36:13 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Thu, 6 Nov 2008 18:36:13 -0500 Subject: [18335fall08] midterm exams vs. final grade Message-ID: Hi gang, Several of you have contacted me with concerns that you may have done badly on the midterm, and were worried that you might have to drop the class even though you have put a lot of work into it. I wanted to reassure you that, as long as you do well on the homeworks and on the final project, you should get a decent grade (B or higher) even if your performance on the midterm was an outlier. Unfortunately (and this has happened to me before, the first time I teach a new course) I got too ambitious on the midterm and as a result your performance on it may not be representative. That means that when I assign letter grades a simple numerical average won't be sufficient; I'll look at your overall work in the course. Drop date is November 19, two weeks from yesterday. Your exams will be graded by next week sometime; feel free to contact me if you want to discuss things further. --SGJ From stevenj.mit at gmail.com Thu Nov 13 20:14:55 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Thu, 13 Nov 2008 20:14:55 -0500 Subject: [18335fall08] nonlinear optimization library NLopt Message-ID: <16717A23-D998-485E-9013-6FBBD3136A60@fftw.org> Hi gang, For those of you who need a canned nonlinear optimization package for your projects (and possibly for one more short problem set), the NLopt library that I've posted may be helpful. I've now posted documentation/tutorials as well as downloading and installation instructions (at least for Unix-like systems): http://ab-initio.mit.edu/nlopt I've also compiled NLopt for the Athena Linux systems in my home directory on Athena. Do add stevenj on Athena, and it is in /mit/stevenj/Public/nlopt_i386_linux2 In particular, the Matlab plugins are in the "matlab" subdirectory. To use them, you will need to add that subdirectory to your Matlab path. In Matlab, do: path(path,'/mit/stevenj/Public/nlopt_i386_linux2/matlab') Then see the online documentation, or type "help nlopt_minimize" in Matlab. --SGJ PS. Let me know if you need a Windows version and we'll try to work something out. MacOS X should be straightforward because it is a Unix system. From stevenj.mit at gmail.com Mon Nov 17 19:58:24 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Mon, 17 Nov 2008 19:58:24 -0500 Subject: [18335fall08] some info on the final project paper Message-ID: Hi gang, As I said in class, the final project is due on the last day of class (Wed., Dec. 10), which officially is the last date that I am allowed to have assignments due. I wanted to give you a few more tips on what I'm expecting your end result to look like. In terms of results, I'm not expecting anything publication-worthy --- small scale tests of known algorithms on known problems is fine. But it should still be clear and convincing. e.g. if you are trying to demonstrate some trend, you should have enough data points and a well- thought-out numerical experiment for that purpose, clearly presented. It's fine to use "canned" software like NLopt, LAPACK, etcetera, implementing the existing algorithms. However, if your paper is about some algorithm X, or it is about a variety of algorithms for some purpose and you find X to be the best, then I do expect you to write at least a proof-of-concept implementation (e.g. in Matlab) of algorithm X in order to show that you understand the algorithm well enough to implement it yourself. Your implementation does not have to be competitive in terms of performance or robustness with production-quality off-the-shelf software, however. In terms of the paper, I expect it to be structured like a research paper, aimed at the level of your peers in the class. It should include 1) introduction - motivate your project, explaining the basic problem your method address and where this problem arises. give some background and history, both of the problem in general and the specific method(s) you are looking at, citing the relevant papers in the literature. give an overview of what you did in the project and of the remainder of the paper 2) methods - describe the algorithms that you are looking at, and the implementation that you used. (Possibly including pseudocode, although not pages of pseudocode, but no actual programming code should go here.) If you compared several off-the-shelf algorithms, you don't need to explain all of them in great detail; it is okay to focus on one or two and given a brief overview of the others you compared. You should have some explanation of *why* the method works, not just how. Depending on how theoretical your focus is, this may include proofs, or it may just consist of simple heuristic explanations. Diagrams are helpful and encouraged! 3) results - convincingly presented graphs and discussion of any numerical experiments you did. In general, I expect you to look at both performance and accuracy (floating-point and/or other approximations) of your algorithm. Ideally, you should also compare to at least one competing approach for the same problem. Obviously, the precise nature of the problem you look at will determine precisely what numerical experiments you perform. For example, if you have an approximate method, you might look at the performance as a function of the required accuracy in the solution. Note also that the best way to measure performance might not be timing measurements (e.g. if you compare C code for one algorithm to Matlab code for another algorithm, timing comparisons might be very misleading because they are mainly comparing C vs. Matlab and not algorithm 1 vs. algorithm 2). For example, if you are looking at different optimization algorithms, counting the number of times the objective function is evaluated to obtain the solution to within a given accuracy might be more appropriate. Or if you are comparing ODE integrators for y' = F(y), you might compare the number of times F(y) is evaluated for a given level of accuracy. 4) discussion of results - explain features you observed. For example, if you looked at roundoff errors, a theoretical analysis of roundoff and conditioning in your algorithm might be appropriate. 5) conclusion - a summary of your findings. ("This algorithm sucks for this problem" is an okay finding, as long as you have convincingly demonstrated that the problem is intrinsic to the algorithm and not merely a flaw or bug in your implementation of it.) As mentioned on the course web page, I expect the formatting of the paper to resemble a paper in the SIAM Journal on Numerical Analysis. (You can find templates on http://www.siam.org/journals/auth- info.php ... also, you can just look at some random papers in that journal to see what they look like.) I don't care about every tiny detail, as long as it is basically similar. Do *not* use preprint format (preprints are normally double spaced); use the single-spaced format like the published journal papers. The paper should be 5-10 pages long, including figures. This does not include source code; you should attach a printout of any code you wrote as an appendix. (Do *not* print out source code you downloaded from elsewhere, unless you substantially modified it. I don't want printouts of all of LAPACK, for example!) --SGJ From stevenj.mit at gmail.com Wed Nov 19 21:05:41 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Wed, 19 Nov 2008 21:05:41 -0500 Subject: [18335fall08] reminder: pset 6 on web page Message-ID: <9DF9A645-F657-49EB-9209-D8A1A83A6E8E@fftw.org> Hi gang, This is just to remind you that pset 6 is posted on the course web page, due December 1st. It should be a short and relatively easy problem set, so that you can focus mainly on your final projects. --SGJ From stevenj.mit at gmail.com Sat Nov 22 17:55:25 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Sat, 22 Nov 2008 17:55:25 -0500 Subject: [18335fall08] pset6 errata, Athena dialup Message-ID: Hi gang, On problem 1, in the last sentence defining a "convex set", there is a typo: there are two x's instead of an x and a y. Also, problem "3" should be problem "2". The updated pset6.pdf is posted on the course page (math.mit.edu/ ~stevenj/18.335/pset6.pdf). Also, for those of you who want to do the problem set via Athena "dialup" (i.e. ssh): you *cannot* use athena.dialup.mit.edu or x.dialup.mit.edu, because those are Sun Solaris machines, and I only compiled the NLopt plugin for Linux/x86. A usable dialup machine is linux.mit.edu (or you can go to an Athena cluster). --SGJ From stevenj.mit at gmail.com Mon Nov 24 18:25:54 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Mon, 24 Nov 2008 18:25:54 -0500 Subject: [18335fall08] office hours Tuesday (tomorrow) 4:30-5:30 Message-ID: <526AA27E-F955-4BE4-BC0C-5B62548D58E9@fftw.org> Hi gang, Since I'm not planning on holding office hours during Thanksgiving (unless any of you happen to be in Philadelphia), you can come to my office tomorrow (Tuesday) instead, from 4:30-5:30pm. --SGJ From stevenj.mit at gmail.com Tue Nov 25 22:28:50 2008 From: stevenj.mit at gmail.com (Steven G. Johnson) Date: Tue, 25 Nov 2008 22:28:50 -0500 Subject: [18335fall08] setting your Matlab path for problem 2 Message-ID: <3570E04E-CE09-443A-8AC5-8E10BF2E7BA3@fftw.org> Hi gang, I noticed that the PDF of the problem set truncates the Matlab instructions (which run off the edge of the page). In Matlab, you need to type: path(path,'/mit/stevenj/Public/nlopt_i386_linux2/matlab') in order to get access to the NLopt commands (after typing "add stevenj" at the Athena prompt). --SGJ