Implicit assumptions – the dark side of computer algebra systems

by Pavel Holoborodko on June 23, 2017

Computer algebra systems are invaluable tools for modern researchers. Although commonly used CAS (Maple and Mathematica) are quite slow at numerical computations with extended precision, still they are main workhorses for doing tedious symbolic simplifications and manipulations on expressions.

However, with all the respect to substantial progress in the area, we want to draw attention to one of the not-so-obvious issues with symbolic simplifications – implicit assumptions. In a course of working with expression, symbolic engine makes certain assumptions about variables involved. This process is automatic and very helpful, as it takes this burden from user’s shoulders.

However, as always with any automation, picture is not that idealistic. Implicit assumptions made by software define the result we get, but nevertheless such assumptions are hidden from the user (at least by default) and not easily accessible. In some situations this leads to completely unexpected and wrong results. In this post we show one of the examples.

Read More

{ 0 comments }

Citations Digest v.9

by Pavel Holoborodko on February 14, 2017

Recent papers citing the toolbox:

Previous issues: digest v.8, digest v.7, digest v.6, digest v.5, digest v.4, digest v.3 and digest v.2.

{ 0 comments }

DevNotes #4. Check status of warning messages from MEX

by Pavel Holoborodko on October 24, 2016

MATLAB allows flexible adjustment of visibility of warning messages. Some, or even all, messages can be disabled from showing on the screen by warning command.

The little known fact is that status of some warnings may be used to change the execution path in algorithms. For example, if warning 'MATLAB:nearlySingularMatrix' is disabled, then linear system solver (operator MLDIVIDE) might skip estimation of reciprocal condition number which is used exactly for the purpose of detection of nearly singular matrices. If the trick is used, it allows 20%-50% boost in solver performance, since rcond estimation is a time consuming process.

Therefore it is important to be able to retrieve status of warnings in MATLAB. Especially in MEX libraries targeted for improved performance. Unfortunately MATLAB provides no simple way to check status of warning message from MEX module.

Article outlines two workarounds for the issue.

Read More

{ 0 comments }

Architecture of eigenproblem solver

by Pavel Holoborodko on October 20, 2016

Introduction

In connection to our previous article on Architecture of linear systems solver we decided to outline structure of eigensolver implemented in our toolbox. As with linear system solver – we have plethora of algorithms targeted for matrices with specific properties. Toolbox analyses input matrices and automatically selects the best matching method to find the eigendecomposition.

Standard eigenproblem, EIG(A)

Rendered by QuickLaTeX.com

Read More

{ 0 comments }

Architecture of linear systems solver

by Pavel Holoborodko on October 7, 2016

Computational complexity of direct algorithms for solving linear systems of equations is O(n3). The only way to reduce enormous effect of cubic growth is to take advantage of various matrix properties and use specialized solvers1.

Toolbox follows this strategy by relying on poly-solver which automatically detects matrix properties and applies the best matching algorithm for the particular case. In this post we outline our solver architecture for full/dense matrices.

Poly-solver for dense input matrices (click on flowchart to see it in higher resolution):

Architecture of linear systems solver in Advanpix toolbox

Toolbox analyses the structure of input matrix, computes its bandwidth, checks symmetry/Hermitianity, determines permutation to convert matrix to trivial cases (diagonal or triangular) if possible. Then solver selects the most appropriate algorithm depending on matrix properties. Special attention is paid to n-diagonal matrices (banded), frequently encountered in solution of PDE.

Read More

{ 2 comments }

Citations Digest v.8

by Pavel Holoborodko on September 20, 2016

Recent papers citing the toolbox:

Previous issues: digest v.7, digest v.6, digest v.5, digest v.4, digest v.3 and digest v.2.

{ 0 comments }

How to write precision independent code in MATLAB

by Pavel Holoborodko on July 21, 2016

One of the main design goals of toolbox is ability to run existing scripts in extended precision with minimum changes to code itself. Thanks to object-oriented programming the goal is accomplished to great extent. Thus, for example, MATLAB decides which function to call (its own or from toolbox) based on type of input parameter, automatically and absolutely transparently to user:

>> A = rand(100);            % create double-precision random matrix
>> B = mp(rand(100));        % create multi-precision random matrix
 
>> [U,S,V] = svd(A);         % built-in functions are called for double-precision matrices
>> norm(A-U*S*V',1)
ans =
      2.35377689561389e-13
 
>> [U,S,V] = svd(B);         % Same syntax, but now functions from toolbox are used
>> norm(B-U*S*V',1)
ans = 
    3.01016831776648753720608552494953562e-31

Syntax stays the same, allowing researcher to port code to multi-precision almost without modifications.

However there are several situations which are not handled automatically and it is not so obvious how to avoid manual changes:

  • Conversion of constants, e.g. 1/3 -> mp('1/3'), pi -> mp('pi'), eps -> mp('eps').
  • Creation of basic arrays, e.g. zeros(...) -> mp(zeros(...)), ones(...) -> mp(ones(...)).

In this post we want to show technique on how to handle these situations and write pure precision-independent code in MATLAB, so that no modifications are required at all. Code will be able to run with standard numeric types 'double'/'single' as well as with multi-precision numeric type 'mp' from toolbox.

Read More

{ 1 comment }

Citations Digest v.7

by Pavel Holoborodko on July 13, 2016

Recent works citing the toolbox:

Previous issues: digest v.6, digest v.5, digest v.4, digest v.3 and digest v.2.

{ 0 comments }

DevNotes #3. Asynchronous Handling of Ctrl-C in MEX

by Pavel Holoborodko on July 2, 2016

There seems to be growing interest in how to detect user interrupt (Ctrl-C) inside compiled MEX library. The main difficulty is that TheMathWorks provides no official API to recognize and handle the situation.

As a workaround, Wotao Yin found undocumented function utIsInterruptPending which can be used to check if Ctrl-C was pressed. The most obvious usage pattern is to include calls to the function in lengthy computational code (loops, etc.) and exit the computations if needed. Collection of various improvements on using utIsInterruptPending can be found in recent Yair Altman’s post.

Unfortunately, despite all these efforts the most important issue was not addressed and was not resolved up to date – asynchronous handling of Ctrl-C.

In order to respond to user interrupt, source code of the MEX module have to be changed to include utIsInterruptPending calls. Every sub-module, every loop of the code needs to be revised. This is not only time-consuming and error-prone process, but also makes pure computational code dependent on MEX API.

Most importantly, it is not possible to do all the modifications if MEX uses third-party libraries with no access to its source code.

The ideal solution would be to avoid any of the changes to computational code in MEX. Here we propose one of the ways to do so.

Read More

{ 0 comments }

Version 3.9.9 Release Notes

by Pavel Holoborodko on May 19, 2016

New version of toolbox includes a lot of updates released over the course of six months. We focused on speed, better support of sparse matrices, special functions and stability. Upgrade to the newest version is highly recommended as it contains critical updates for all platforms.

Short summary of changes:

  1. The Core
    • All elementary mathematical functions have been heavily optimized for quadruple precision and now enabled with sparse matrices support. This results in serious performance boost:
      % < 3.9.9:
>> A = 100*mp(rand(1000,1000)-0.5);
>> B = 100*mp(rand(1000,1000)-0.5);
 
>> tic; atan2(A,B); toc;
Elapsed time is 18.056319 seconds.
 
>> tic; log(A); toc;
Elapsed time is 31.506463 seconds.
      % 3.9.9
>> A = 100*mp(rand(1000,1000)-0.5);
>> B = 100*mp(rand(1000,1000)-0.5);
 
>> tic; atan2(A,B); toc;
Elapsed time is 0.262123 seconds.   % ~70 times faster
 
>> tic; C = log(A); toc;
Elapsed time is 0.843535 seconds.   % ~37 times faster

      This improvement covers all elementary and majority of special functions. Please note, all appropriate functions handle branch cuts correctly and support signed zeros to the contrary of MATLAB.

      • Read More

{ 0 comments }

← Previous Entries

Next Entries →