July 2011 - petsc-dev - mailman3.cels.anl.gov

Re: [petsc-dev] KSP convergence test based on error on residual
by Mark F. Adams 18 Jul '11

18 Jul '11

On Jul 17, 2011, at 10:31 PM, Jed Brown wrote: > On Sun, Jul 17, 2011 at 21:23, Mark F. Adams <mark.adams(a)columbia.edu> wrote: > Humm, the only linear algebra proof that I know gives bounds on the error of the form > > | error |_2 <= Condition-number * | residual |_2, > > This looks like relative error. Yes, I was confused last night, JFK will do that :) Mark > > > for SPD matrices of course. This is pessimistic but I'm not sure how you could get a bound on error with only the lowest eigen value ... > > Suppose you have > > | A x - b | < c > > Then there is some y such that > > A (x + y) - b = 0 > > and for which > > |A y| < c > > Suppose s is the smallest singular value of A, thus 1/s is the largest singular value of A^{-1}. Then > > |y| = | A^{-1} A y | <= (1/s) |A y| < c/s. > > So you can bound the absolute error in the solution if you know the residual and the smallest singular value.

1 0

Re: [petsc-dev] KSP convergence test based on error on residual
by Barry Smith 17 Jul '11

17 Jul '11

Jed beat me to it, For the symmetric positive definite case one just uses the definition of the largest eigenvalue e^T e r^T A^{-1} A^{-1} r \lambda_{max} (A^(-2)) = 1 ------------ = --------------------------- <= ----------- r^T r r^T r \lambda^2_{min}(A) When I did my dissertation I always computed for absolute error reduction using the minimum eigenvalue for the SPD case the and the singular value for the general case. When I started working with Bill and he only cared about the solution to a nonlinear problem I lost the habit but it really should be incorporated in PETSc. Barry On Jul 17, 2011, at 9:31 PM, Jed Brown wrote: > On Sun, Jul 17, 2011 at 21:23, Mark F. Adams <mark.adams(a)columbia.edu> wrote: > Humm, the only linear algebra proof that I know gives bounds on the error of the form > > | error |_2 <= Condition-number * | residual |_2, > > This looks like relative error. > > > for SPD matrices of course. This is pessimistic but I'm not sure how you could get a bound on error with only the lowest eigen value ... > > Suppose you have > > | A x - b | < c > > Then there is some y such that > > A (x + y) - b = 0 > > and for which > > |A y| < c > > Suppose s is the smallest singular value of A, thus 1/s is the largest singular value of A^{-1}. Then > > |y| = | A^{-1} A y | <= (1/s) |A y| < c/s. > > So you can bound the absolute error in the solution if you know the residual and the smallest singular value.

1 0

Re: [petsc-dev] KSP convergence test based on error on residual
by Mark F. Adams 17 Jul '11

17 Jul '11

On Jul 16, 2011, at 5:17 PM, Jed Brown wrote: > On Sat, Jul 16, 2011 at 16:11, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > Jed, > > I just remembered something I should have said when we talked about the rewrite of the KSPSPECEST stuff. > > If one has the bound on the smallest eigenvalue of the (preconditioned) operator then ones convergence test can take that into account and know that the 2-norm of the error of the linear solver (as opposed to the 2 norm of the residual) is less than some tolerance. Of course the KSPSPECEST can give us this information, even though Mark doesn't believe it is accurate enough :-), with enough iterations it can be. > > I would expect it to become a good approximation when the KSP has converged on the low-frequency modes. I think Mark's I would too, but this would be an experiment that I'd like to see. For instance, solve a largish 5 point stencil Laplacian (or whatever) with a simple solver (and multilevel solver if you get ambitious) and plot the history of the lowest (and highest) eigen estimates vs. iteration number. > objection is that a few iterations are usually nowhere near actually converging, so you can only use the estimate in a meaningful way to estimate the high end of the spectrum. Yes, thats right. My comments on accuracy were in the context of eigen estimates for smoothers, where getting the lowest bound would be tantamount to solving the systems with the smoother (ie, not practical), an its not really needed for smoothers (but it would be nice if it were around). Mark > > So ideally we'd have options that allowed convergence tests to use the estimate of the error norm instead of just the residual norm. > > How would you suggest handling restarts?

1 0

Re: [petsc-dev] KSP convergence test based on error on residual
by Jed Brown 17 Jul '11

17 Jul '11

On Sun, Jul 17, 2011 at 21:23, Mark F. Adams <mark.adams(a)columbia.edu>wrote: > Humm, the only linear algebra proof that I know gives bounds on the error > of the form > > | error |_2 <= Condition-number * | residual |_2, > This looks like relative error. > > for SPD matrices of course. This is pessimistic but I'm not sure how you > could get a bound on error with only the lowest eigen value ... > Suppose you have | A x - b | < c Then there is some y such that A (x + y) - b = 0 and for which |A y| < c Suppose s is the smallest singular value of A, thus 1/s is the largest singular value of A^{-1}. Then |y| = | A^{-1} A y | <= (1/s) |A y| < c/s. So you can bound the absolute error in the solution if you know the residual and the smallest singular value.

1 0

Re: [petsc-dev] KSP convergence test based on error on residual
by Mark F. Adams 17 Jul '11

17 Jul '11

On Jul 16, 2011, at 5:11 PM, Barry Smith wrote: > > Jed, > > I just remembered something I should have said when we talked about the rewrite of the KSPSPECEST stuff. > > If one has the bound on the smallest eigenvalue of the (preconditioned) operator then ones convergence test can take that into account and know that the 2-norm of the error of the linear solver (as opposed to the 2 norm of the residual) is less than some Humm, the only linear algebra proof that I know gives bounds on the error of the form | error |_2 <= Condition-number * | residual |_2, for SPD matrices of course. This is pessimistic but I'm not sure how you could get a bound on error with only the lowest eigen value ... Mark > tolerance. Of course the KSPSPECEST can give us this information, even though Mark doesn't believe it is accurate enough :-), with enough iterations it can be. So ideally we'd have options that allowed convergence tests to use the estimate of the error norm instead of just the residual norm. > > Barry > >

1 0

Re: [petsc-dev] KSP convergence test based on error on residual
by Barry Smith 16 Jul '11

16 Jul '11

On Jul 16, 2011, at 4:17 PM, Jed Brown wrote: > On Sat, Jul 16, 2011 at 16:11, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > Jed, > > I just remembered something I should have said when we talked about the rewrite of the KSPSPECEST stuff. > > If one has the bound on the smallest eigenvalue of the (preconditioned) operator then ones convergence test can take that into account and know that the 2-norm of the error of the linear solver (as opposed to the 2 norm of the residual) is less than some tolerance. Of course the KSPSPECEST can give us this information, even though Mark doesn't believe it is accurate enough :-), with enough iterations it can be. > > I would expect it to become a good approximation when the KSP has converged on the low-frequency modes. I think Mark's objection is that a few iterations are usually nowhere near actually converging, so you can only use the estimate in a meaningful way to estimate the high end of the spectrum. > > So ideally we'd have options that allowed convergence tests to use the estimate of the error norm instead of just the residual norm. > > How would you suggest handling restarts? Restarts (at least my understanding) ruin the approximation and start all over again (perhaps there is some way to handle this). Regardless if one is solving two or more linear systems with the same (over very similar) matrices one could get the good estimate during the first solve (over solving if needed with a higher restart to get the good eigenvalue estimate) and then use that estimate for the later solvers, which don't need to be over solves. I just brought this up to see if we can fit this into the same framework needed for the estimates used for Chebychev. Barry

1 0

Re: [petsc-dev] KSP convergence test based on error on residual
by Jed Brown 16 Jul '11

16 Jul '11

On Sat, Jul 16, 2011 at 16:11, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > Jed, > > I just remembered something I should have said when we talked about the > rewrite of the KSPSPECEST stuff. > > If one has the bound on the smallest eigenvalue of the (preconditioned) > operator then ones convergence test can take that into account and know that > the 2-norm of the error of the linear solver (as opposed to the 2 norm of > the residual) is less than some tolerance. Of course the KSPSPECEST can give > us this information, even though Mark doesn't believe it is accurate enough > :-), with enough iterations it can be. I would expect it to become a good approximation when the KSP has converged on the low-frequency modes. I think Mark's objection is that a few iterations are usually nowhere near actually converging, so you can only use the estimate in a meaningful way to estimate the high end of the spectrum. > So ideally we'd have options that allowed convergence tests to use the > estimate of the error norm instead of just the residual norm. > How would you suggest handling restarts?

1 0

KSP convergence test based on error on residual
by Barry Smith 16 Jul '11

16 Jul '11

Jed, I just remembered something I should have said when we talked about the rewrite of the KSPSPECEST stuff. If one has the bound on the smallest eigenvalue of the (preconditioned) operator then ones convergence test can take that into account and know that the 2-norm of the error of the linear solver (as opposed to the 2 norm of the residual) is less than some tolerance. Of course the KSPSPECEST can give us this information, even though Mark doesn't believe it is accurate enough :-), with enough iterations it can be. So ideally we'd have options that allowed convergence tests to use the estimate of the error norm instead of just the residual norm. Barry

1 0

Re: [petsc-dev] new configuration/compile system for PETSc
by Jed Brown 10 Jul '11

10 Jul '11

On Sun, Jul 10, 2011 at 21:11, Dmitry Karpeev <karpeev(a)mcs.anl.gov> wrote: > This is probably implied by what's already on the list, but we need an > easy way for the *users* to build individual > examples, as well as to add new examples, when they experiment with > PETSc. > This is the easiest possible case to support. We are focusing on the interoperability and multi-dependency cases because they are actually hard.

1 0

Re: [petsc-dev] new configuration/compile system for PETSc
by Dmitry Karpeev 10 Jul '11

10 Jul '11

This is probably implied by what's already on the list, but we need an easy way for the *users* to build individual examples, as well as to add new examples, when they experiment with PETSc. The ability to incorporate PETSc into new and/or existing codes that use other packages (that aren't a part of the PETSc build) has already been discussed. It's a natural extension of writing and building small examples. It's probably implied by one of the below list items, but I'm not sure which :-), so I thought I'd mention it again. Dmitry. On Sat, Jul 9, 2011 at 10:17 PM, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > Ok, here's the current list of requirements. What is missing? > > > Requirements: > X 1) Portability to Windows, Cygwin, Unix (all versions) > 2) Compatible with GUI development systems (Xcode, Eclipse, Emacs, ...) > 3) Able to run parallel configures and builds (on shared memory system enough?, distcc?) > 4) Able to work with batch systems > 5) Able to handle dependencies between packages (given dependencies between packages builds everything in the correct order) > 6) Able to utilize clang and similar systems > 7) Works seamlessly with GNU autoconf, Cmake, pkconfig packages (that is will build these packages automatically and maybe generate them) > 8) Can download and install packages by given URL > 9) Easy to add configurations for packages such as SuperLU, etc that have no decent configuration > x 10) Can test for available functionalities (include files, etc) > X 11) Easy to add new types of compilers, new tests > 12) Does dependency analysis and rebuilds only what needs to be rebuilt > 13) Able to manage test suites > 14) Compatible with and able to use revision control systems > 15) Completely command-line controlled but also with a GUI frontend that gives one full control as well > 16) Able to build for bizarre-assed systems like the iPAD and GPUs. > 17) Able to manage the concept of abstract packages such as MPI and BLAS/LAPACK and particular implementations > 18) Able to handle already installed packages and detect if that package uses something incompatable with other packages: for example HDF5 installed with OpenMPI and someone building other packages with MPICH. > 19) Able to manage several different compilers of the same type (for example 2 C compilers) being used for different packages. > 20) Incrementable builds, that is more packages can be installed later based on packages already installed. Say add SLEPc later. > > > X - does, x - does some > > > On Jul 9, 2011, at 7:45 PM, Dmitry Karpeev wrote: > >> Observe that PETSc's configure deals with the problem of consistently >> configuring MULTIPLE >> packages, while most tools I have heard of typically deal with a >> SINGLE package. That's a >> qualitative difference, in my opinion. >> >> Separately, I would suggest having the new build system allow the user >> to install PETSc in one >> go. Something like 'cll install --with-clanguage=c++ ...', because >> it's rare for users to stop after >> configuring, and then end up executing an easily automatable sequence of steps: >> configure --with-clanguage=c++ ... >> make PETSC_DIR= ... all >> make PETSC_DIR= ... PETSC_ARCH=... test >> >> Of course, we should provide intermediate stages as well -- 'cll >> configure' -- etc. >> In particular, if cll were able to configure "arbitrary" collections >> of packages, it may be desirable >> to leave the "top" package configured, but not built, as it has to be >> built repeatedly (as part of >> a development cycle) using make or cmake, etc. >> >> Dmitry. >> >> On Sat, Jul 9, 2011 at 7:37 PM, Dmitry Karpeev <karpeev(a)mcs.anl.gov> wrote: >>> On Sat, Jul 9, 2011 at 7:18 PM, Harald Pfeiffer >>> <pfeiffer(a)cita.utoronto.ca> wrote: >>>> We happen to use Petsc with our own makefiles. PETSc is compiled entirely >>>> separately (or we use system-provided PETSc-modules). We then manually set >>>> the appropriate include- and library-paths in our makefiles, for example: >>>> >>>> PETSC_INCLUDE = -I$(PETSC_DIR)/include -I$(PETSC_DIR)/$(PETSC_ARCH)/include >>>> PETSC_LIB = -L$(PETSC_DIR)/$(PETSC_ARCH)/lib -lpetsc -lX11 >>>> ... >>>> other stuff here >>>> ... >>>> ARCH_INCLUDE = $(PETSC_INCLUDE) ... >>>> ARCH_LIB_PARALLEL = $(HDF_LIB) $(FFTW_LIB) $(PETSC_LIB) .... >>>> >>>> >>>> Not elegant, but has been working like a charm for the last 12 years. >>> >>> I'm not saying it can't be made to work. >>> I'm saying it might not be trivial for someone just starting to use >>> PETSc and not even necessarily >>> that familiar with make: there are a lot of potential users like that. >>> And even for more sophisticated >>> users it might take a while to work out the kinks. >>> >>> Dmitry. >>> >>>> >>>> >>>> Harald >>>> >>>> >>>> >>>> >>>> >>>> >>>> On 7/10/11 1:02 AM, Dmitry Karpeev wrote: >>>>> >>>>> On Sat, Jul 9, 2011 at 6:42 PM, Jed Brown<jedbrown(a)mcs.anl.gov> wrote: >>>>>> >>>>>> On Sat, Jul 9, 2011 at 18:30, Dmitry Karpeev<karpeev(a)mcs.anl.gov> wrote: >>>>>>> >>>>>>> If a user could write a >>>>>>> simple foo.py that configured/built their >>>>>>> favorite package with PETSc as a dependency, they could then proceed >>>>>>> to modify the FOO code and jack >>>>>>> PETSc into it. >>>>>> >>>>>> But this just a different form of asking them to adopt our build system, >>>>>> except that makefiles are a de-facto standard and our system won't be >>>>>> familiar to anyone. Any system has to be easily usable from other systems >>>>>> (at least makefiles, automake, and cmake). >>>>> >>>>> Yes, but there is also a practical problem: an engineer or a scientist, >>>>> not >>>>> intimately familiar with automake, cmake, etc., has taken the effort >>>>> to understand >>>>> PETSc so that our linear solvers can be substituted for FOO's. How can we >>>>> make it easier for these people to insert PETSc into their code? Here >>>>> I only mean >>>>> the build process. Maybe making them write foo.py is not the right >>>>> approach, >>>>> but we should have a usable approach (and, maybe, an example of doing it). >>>>> >>>>> In particular, is it sufficient to export linklibs, or do we also need >>>>> to export the >>>>> compiler (e.g., to ensure consistent Fortrant name mangling)? There are >>>>> a good number of Fortran users that want to use PETSc too. >>>>> >>>>> Dmitry. >>>> >>>> -- >>>> Harald Pfeiffer >>>> Assistant Professor >>>> Cdn. Institute for Theoretical Astrophysics >>>> University of Toronto >>>> pfeiffer(a)cita.utoronto.ca >>>> Tel. ++1 416-978-8497 >>>> >>>> >>> > >

1 0