Monday, September 30, 2013

Are MATLAB containers.Map more efficient?

UPDATE 2015-02-10 I learned something interesting recently that sheds some light on the answer to this question. I believe that MATLAB's containers.Map is a wrapper around Java's java.util.HashMap. A hash map or hash table is a zeroth order look-up table that uses a hash of the look-up key or index for tables as the address in memory that contains the corresponding value. Therefore it doesn't matter how big the hash map or hash table is, MATLAB (or Java) can immediately return the contents given the key. Since the hash is guaranteed to be unique for any given index or key, the memory address of the value will also be unique. So the answer to the question, "Are MATLAB containers.Map more efficient?" is absolutely and without any doubt a loud and resounding, "Yes!" QED

MATLAB's containers.Map's are similar to a Java HashMap or a Python dictionary. They have been around at least since 2008b believe it or not. They were billed as
Fast Key Lookup Provided with New Map Data Structure
when they were introduced. See Programming Fundamentals in 2008b Release Notes. How much memory do they realy take up? MATLAB doesn't say. It seems like they're smaller, but you'll soon see that every containers.Map is always 112 Bytes. How much faster can they really be? My guess is they are really only more efficient for really large data, that are only nested with other containers.Map's of primitive types (IE integers, doubles, &c.).

They have some limitations in subassignment and indexing.

For example:
  • If the value of map('k1') is also a containers.Map,
  • map('k1')('k2')
    Error: ()-indexing must appear last in an index expression.
    then this is invalid because MATLAB only allows one pair of parentheses which must appear last. So you'll have to split this into two commands. This also allows assignment into the nested containers.Map ...
    val_is_map = map('k1') % make a temp handle to the top level containers.Map
    val_is_map('k2') = new_value % assignment using the handle also changes the containers.Map it points to
    test = map('k1') % make another handle to test the original containers.Map was updated
    test('k2') == new_value % true
    ... because containers.Map's are handles (IE pointers) so changing the value of a copied containers.Map changes the source.
  • If the value of map('k1') is a structure,
  • map('k1').field = 'foo'
    Error using containers.Map/subsasgn
    Only one level of indexing is supported by a containers.Map.
    then this is also not valid because only the top level of containers.Map can be assigned.
  • Finally if map('k1') is a cell array, then good luck trying to index it.
>> dict = containers.Map({'all','amend','author','msg'}, ...
       {{'-a','--all',true}, ...
       {[],'--amend',true}, ...
       {[],'--author',true}, ...
       {'-m','--message',false}})

dict = 

  Map with properties:

        Count: 4
      KeyType: char
    ValueType: any

>> s = struct('all',{'-a','--all',true}, ...
       'amend',{[],'--amend',true}, ...
       'author',{[],'--author',true}, ...
       'msg',{'-m','--message',false})

s = 

1x3 struct array with fields:

    all
    amend
    author
    msg

>> c1 = {{'all','-a','--all',true}, ...
       {'amend',[],'--amend',true}, ...
       {'author',[],'--author',false}, ...
       {'msg','-m','--message',false}}

c1 = 

    {1x4 cell}    {1x4 cell}    {1x4 cell}    {1x4 cell}

>> c2 = {'all','-a','--all',true; ...
       'amend',[],'--amend',true; ...
       'author',[],'--author',false; ...
       'msg','-m','--message',false}

c2 = 

    'all'       '-a'    '--all'        [1]
    'amend'       []    '--amend'      [1]
    'author'      []    '--author'     [0]
    'msg'       '-m'    '--message'    [0]

>> whos
  Name      Size            Bytes  Class

  dict      4x1               112  containers.Map
  s         1x3              1670  struct
  c1        1x4              2344  cell
  c2        4x4              1896  cell

Sunday, September 29, 2013

MATLAB syntax for Java inner objects

MATLAB is a Java (and .NET) interpreter, yay!
using-java-libraries-in-matlab
But calling inner objects can be tricky in MATLAB. Use the `javaMethod` and `javaObject` builtins. All the examples are from org.eclipse.jgit
javamethod
javaobject

Constants

These are the easiest of all. Though not technically an inner anything, a constant could be confusing, but it is called exactly as it would be in Java or MATLAB.
    filesystem = org.eclipse.jgit.util.FS.DETECTED
FS is a the filesystem class in org.eclipse.jgit.util pacakge. Its constant DETECTED can be accessed using regular dot notation.
org/eclipse/jgit/util/FS

Enumeration of an inner class

This is where it starts to get tricky. A nested or inner class is created in a separate class file preceded with a dollar sign. MATLAB uses the same notation, but only as a string in the javaMethod command.
    NOTRACK = javaMethod('valueOf', ...
        'org.eclipse.jgit.api.CreateBranchCommand$SetupUpstreamMode', ...
        'NOTRACK')
The `CreateBranchCommand has a nested class called `SetupUpstreamMode`. Access it in MATLAB with a dollar symbol, "$", instead of dot notation, but access it using `javaMethod`. For example it has several enumerations. `NOTRACK` is an enumeration of `SetupUpstreamMode`. Calling the `valueOf()` method of `SetupUpstreamMode` and passing it the string, "NOTRACK" inside the MATLAB builtin `javaMethod` does the trick.
org/eclipse/jgit/api/CreateBranchCommand
org/eclipse/jgit/api/CreateBranchCommand.SetupUpstreamMode
org/eclipse/jgit/api/CreateBranchCommand.SetupUpstreamMode.html#NOTRACK

Construct an inner class object

This is also easy.
    user = javaObject('org.eclipse.jgit.transport.CredentialItem$Username')
Username is an static nested class of CredentialItem. Access it using the dollar sign instead of dot notation in a call to `javaObject`.
org/eclipse/jgit/transport/CredentialItem.Username

And that's pretty much that. There are some other Java tools, like javaArray, javaMethodEDT & javaObjectEDT. I'll update this more later. Promise.

Credit for MATLAB brush: Will Schleter. Thanks!

Friday, September 20, 2013

IPOPT as non-linear solver for MATLAB

You have a non-linear problem to solve but not the MATLAB Optimization Toolbox?
  1. First download the IPOPT mex and m-files, and extract to your MATLAB search path.
  2. Make an m-file that defines your objective and constraints, gradient and Jacobian.
  3. Credit for MATLAB brush: Will Schleter. Thanks!
  4. Other non-linear solvers for MATLAB
  5. Perfect for solving a staggered mesh.
  6. If you were using Python you could use optimization routines in SciPy.
function [x,info] = myNonLinearProblem(x0, auxdata)
%MYNONLINEARPROBLEM Solves my non-linear problem
% [X,INFO] = MYNONLINEARPROBLEM[X0,AUXDATA]
% returns solution, X, and INFO to my non-linear problem
% X0 is the initial guess
% AUXDATA are any additional arguments my non-linear problem
% requires

x0 = x0(:); % initial guess

%% constraints
%set all of your equations as constraints
funcs.constraints = @constraints;
% constraints require a Jacobian
funcs.jacobian = @jacobian;
% Jacobians require a sparsity structure
funcs.jacobianstructure = @jacobianstructure;
% set upper and lower bounds of constraints to zero
options.cl = zeros(size(x0)); % lower bounds
options.cu = zeros(size(x0)); % lower bounds

%% objective
% set the objective sum of the squares
funcs.objective = @objective;
% objective requires a gradient
funcs.gradient = @gradient;

%% options
% set Quasi-Newton option
options.ipopt.hessian_approximation = 'limited-memory';

%% solve
[x,info] = ipopt_auxdata(x0,funcs,options);
end

% x & auxdata must be passed as only args to
% objective, gradient, constraints and jacobian

function f = objective(x,auxdata)
% objective is the sum of the squares of the residuals
f = residual(x,auxdata);
f = f(:);
f = f'*f;
end

function g = gradient(x,auxdata)
[f,j] = residual(x,auxdata);
f = f(:);
g = f'*j;
end

function f = constraints(x,auxdata)
f = residual(x,auxdata);
f = f(:);
end

% Jacobian and Jacobian structure must be sparse

function j = jacobian(x,auxdata)
% rows correspond to each constraint
% columns correspond to each x
[~,j] = residual(x,auxdata);
j = sparse(j);
end

function j = jacobianstructure(x)
% x is the only arg passed to Jacobian structure
% assuming closed system of equations
% # of constraints = degrees of freedom
% therefore Jacobian matrix will be square
j = sparse(ones(size(x)));
end

% put the equations and their derivatives here
% unfortunately IPOPT is not a Jacobianless solver :(

function [f,j] = residuals(x,auxdata)
% calculate your residuals here
% f1(x,auxdata) = lhs1(x,auxdata) - rhs1(x,auxdata) = 0
% f2 = ...
% j1(x,auxdata) = [df1/dx1, df1/dx2, ...]
% j2 = ...
end
Fork me on GitHub