Windows Vista Bug List
I've been using Windows Vista Beta 2 (via the customer preview program) for about two weeks now.
Vista is aptly named. Vista provides a vista to the future. Unfortunately, it is merely a vista to the future, and not the future itself. Vista has potential, but is currently unstable, buggy, and idiosynchratic.
I like Vista. It has potential. It simply isn't quite there yet. Hopefully, RC1 will fix many problems.
Without further ado, here are the bugs I've found in Vista Beta 2.
mstsc.exe
1. On a Vista machine, use mstsc.exe to connect to another machine (I've used a WinXP machine, not another Vista machine). Maximize the remote desktop window.
2. On the WinXP machine (machine 2), log back on without disconnecting from the Vista session.
3. Return to the Vista machine and click through the "you've been disconnected" error. Reconnect to the machine. The "menu" at the top of the remote desktop session does not appear, nor is there any way to make it appear. In fact, the only way to exit from the new remote desktop session is to ctrl-alt-del and load task manager.
adding a printer
While using a Vista machine from mstsc.exe on a WinXP machine, attempt to add a TCP/IP printer (add a printer, local printer, create a new port, blah-printer.microsoft.com, ...)
After entering the printer address or IP address, clicking next will yield the error "The TCP/IP wizard page was not able to load" or something like that. The upshot: you cannot add a TCP/IP printer over a remote desktop connection. Ouch!
So far, the count is just at two, if you remove the 10's of crashes I've had that were "due to drivers."
Top Gun Drinking Game
Oops, we have a slight diversion.
Without further explanation, I present the
ICME Top Gun Drinking Game.
Drink for all ...
1. homosexual references,
1b. Exception: finish your drink during the volleyball game.
2. theme songs (i.e. Danger Zone, You Never Close Your Eyes, etc.),
3. lock tones,
4. utterances of Maverick, Goose, or Ghostrider,
5. references to MIG, bogey,
6. landings and takeoffs,
7. Goose deaths,
8. facebook references (i.e. "Too close for missiles, switching to guns").
Retrospectively, 1, 4, and 5 are more than sufficient. Type 3 drinks are to push you over the edge. The rest are to maintain a thorough buzz throughly the movie/game.
Reading Cluto Files in Matlab (Part I)
Today, let’s see a Matlab solution to reading and writing CLUTO data files. CLUTO is a clustering toolkit by George Karypis at U of Minn. There are FOUR possible input files CLUTO might see.
- Dense Graph
- Sparse Graph
- Dense Matrix
- Sparse Matrix
The difference between the dense and sparse files is simply a matter of header information. Let’s describe a few CLUTO files.
- Suppose we have a 5-node line graph
v1 <-> v2 <-> v3 <-> v4 <-> v5
In dense graph format, this graph is
5 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0
In sparse graph format, this graph is
5 8 2 1 1 1 3 1 2 1 4 1 3 1 5 1 4 1
To wit, the dense graph format is merely an explicit specification of the adjacency matrix for the graph with a single line specifying the number of vertices. The sparse graph format is a sparse adjacency representation. The sparse adjacency is somewhat strange in that it uses 1 based columns, and implicit rows.
More formally, the sparse adjacency structure has 1 line of header information:
<number of vertices> <number of edges*2>
and the i+1th line of the file contains
adj_1 weight_1 adj_2 weight_2 … adj_d weight_d
where adj_j is the jth adjacent vertex and weight_j is the weight of that edge and d is the degree of the ith vertex. The input must be symmetric.
The sparse and dense matrix file formats are similar. The difference is the matrices involved are not square which changes the header.
- dense matrix header:
<number of rows> <number of columns> - sparse matrix header:
<number of rows> <number of columns> <number of nonzeros>
The dense matrix format is just a row-by-row listing of the elements of the matrix. The sparse matrix format is a sparse row-by-row listing. In the sparse matrix format, the i+1th line of the file contains information about the non-zeros in row i.
column_1 value_1 column_2 value_2 … column_d value_d
Coming next, we’ll see how to read these files in Matlab using a combination of mex files and scripts.
Sparse Matrix File Formats
Sparse matrix file formats bug me. Literally, they cause me pain. Everyone uses a slightly different sparse matrix file format and they are all very close, but have slight peculiarities.
I have two ways of dealing with this problem: i) give up; or ii) figure something out. I chose ii. My solution is two-fold. First, I design Matlab codes to read and write the different formats. Second, I design templated C++ codes to read and write the different formats. The Matlab solution allows me to get up and running quickly and is sufficient for infrequent datasets. The C++ solution is more robust and allows my C++ programs to read and write these formats as well.
More coming soon...
Sorting Two Arrays Simultaneously
Suppose, for the sake of this article, that you have two arrays in C++ with the same number of element. For example,
int a1[] = {5, 8, 9, 1, 4, 3, 2};
double v[] = {3., 4., 5., 2., 1., 9., 8.};
Now, for reasons that perhaps only I care about. I want to sort the array a1, and permute v in according to the same permutation.
// a1 = {1, 2, 3, 4, 5, 8, 9}
// v = {2., 8., 9., 1., 3., 4., 5.,}
(For those who care and who know what I'm talking about. I have a compressed sparse row matrix represented in the AIJ format and I want to sort the element of each row in increasing order so I can do O(log n) binary search to determine if an element exists. However, as always, the problem is more generic than the instance I care to solve.)
To wit, I wish to sort one array and "take the other" along for a ride.
This problem has a few trivial solutions:
1. Sort the array a1 implicitly by sorting a permutation vector that indexes into a1. Then permute a1, and v by this array.
2. Write a custom sorting routine that does the operation for this special case.
3. Try to shoehorn this problem into an existing sorting array.
In terms of performance, the fastest solution is probably 2. The second fastest is probably 1. Finally, 3. is likely the slowest.
Solution 3, however, has two huge advantages. First, I don't have to write my own sorting routine. This is important as writing a general purpose sort is somewhat non-trivial. Also, it is fairly likely that the input to the sort will be nearly sorted so I can't use a general purpose quicksort routine which has O(n^2) performance on a sorted array. The second advtange is that it does not require extra memory as solution 1 does. In fact, solution 1 requires quite a bit of extra memory. While it is a tractable amount, it is nonetheless superfluous.
Thus, I decided to look at solution 3. Between STL and Boost, there are quite robust and generic C++ sorting libraries. How hard could this be? Maybe 20, 30 minutes of work?
Quickly, I realized how such thoughts were hopelessly naive.
In a nutshell, the requirements are:
1. Use the C++ STL sorting routine (which has good O(n log n) worst case performance).
2. Do not create extra memory for the sort.
Thankfully, I did not impose any sort of "performance" requirement on myself. In fact, many of the arrays will be rather small; so performance for large arrays is not quite so important.
First, C++ STL sort does not work on boost's zip_iterators, which would have been the natural solution. In fact, there seem to be a number of debates on this matter; and more generally on the requirements of iterators, zip_iterators, and the STL Sort function.
http://user.it.uu.se/~krister/Research/iterators.pdf
http://lists.boost.org/Archives/boost/2004/07/68758.php
http://web.onetel.com/~anthony_w/cplusplus/pair_iterators.pdf
http://cplusplus.anthonyw.cjb.net/
Second, the fundamental problem is that "pairs" of array references do not behave like they should for things to work nicely. That is, there are no clean generalizations of a set of pointers. The best that exists is the boost::tuple class with a set of reference. However, that class fails because references and values are quite strange and do not behave quite like you think.
Instead, I simply decided to abuse the notation of an iterator and write something that works.
This involved writing, effectively, a non-conforming iterator where the reference of the value type is not the same as the reference type.
Here is the code for anyone who cares. (This is a slightly modified version from my code, so it may not compiler, but the fixes should be trivial.)
template <class SortIter, class PermuteIter>
struct sort_permute_iter_helper_type
{
typedef boost::tuple<
typename std::iterator_traits<SortIter>::value_type,
typename std::iterator_traits<PermuteIter>::value_type >
value_type;
typedef boost::tuple<
typename std::iterator_traits<SortIter>::value_type&,
typename std::iterator_traits<PermuteIter>::value_type& >
ref_type;
};
template <class SortIter, class PermuteIter>
class sort_permute_iter
: public boost::iterator_facade<
sort_permute_iter<SortIter, PermuteIter>,
typename sort_permute_iter_helper_type<
SortIter, PermuteIter>::value_type,
std::random_access_iterator_tag,
typename sort_permute_iter_helper_type<
SortIter, PermuteIter>::ref_type,
typename std::iterator_traits<SortIter>::difference_type
>
{
public:
sort_permute_iter()
{}
sort_permute_iter(SortIter ci, PermuteIter vi)
: _ci(ci), _vi(vi)
{
}
SortIter _ci;
PermuteIter _vi;
private:
friend class boost::iterator_core_access;
void increment()
{
++_ci; ++_vi;
}
void decrement()
{
--_ci; --_vi;
}
bool equal(sort_permute_iter const& other) const
{
return (_ci == other._ci);
}
typename
sort_permute_iter_helper_type<
SortIter, PermuteIter>::ref_type dereference() const
{
return (typename
sort_permute_iter_helper_type<
ColIter, PermuteIter>::ref_type(*_ci, *_vi));
}
void advance(difference_type n)
{
_ci += n;
_vi += n;
}
difference_type distance_to(sort_permute_iter const& other) const
{
return ( other._ci - _ci);
}
};
template <class SortIter, class PermuteIter>
struct sort_permute_iter_compare
hehe: public std::binary_function<
typename sort_permute_iter_helper_type<
SortIter, PermuteIter>::value_type,
typename sort_permute_iter_helper_type<
SortIter, PermuteIter>::value_type,
bool>
{
typedef
typename sort_permute_iter_helper_type<
SortIter, PermuteIter>::value_type T;
bool operator()(const T& t1, const T& t2)
{
return (boost::get<0>(t1) < boost::get<0>(t2));
}
};
template <class SortIter, class PermuteIter>
sort_permute_iter<SortIter, PermuteIter>
make_sort_permute_iter(SortIter ci, PermuteIter vi)
{
return sort_permute_iter<SortIter, PermuteIter>(ci, vi);
};
Finally, then, we can write the following sort routine for our two arrays and get the correct result:
std::sort(make_sort_permute_iter(&a1[0],&v[0]),
make_sort_permute_iter(&a1[0]+7,&v[0]+7),
sort_permute_iter_compare());
Wow. That was a lot of work. I hope someone finds it useful.
Wine Page Added
I used to have a wine page on my Stanford web-page. I'm going to remove that one soon and move the page here.
To get the process started, check out the new wine page. The page basically has summaries of the best wine column I read. It also serves as a place to collect notes on what to buy/not buy in stores these days.
Maybe eventually, I'll add my own reviews, who knows.
3 March 2006 -- Paper of the week
Quantum Computing as Geometry [http://www.sciencemag.org/cgi/content/full/311/5764/1133]
This paper addresses an important aspect of quantum computing. The authors show that designing a quantum circuit is equivalent to minimizing the difference between two linear operators. Further, the "cost" of the circuit (in number of gates) is proportional to the minimum geodesic (shortest path) distance between the trivial operator and the desired quantum operator.
Intriguingly, the authors make the statement that we can use their results to find the initial point to begin a search for the quantum circuit; but (and this is an important but) we do not know the initial velocity along the shortest path. In all likelihood, this problem will be resolved in the future. Nevertheless, this statement harks to the uncertainty principle. Suppose a similar result is true for these Riemannian spaces? We cannot know both the initial search position and the initial velocity. Again, probably my naïveté.
Still fantastically cool... enjoy reading!
28 February 2006
I decided tonight I need to start charging consulting rates.
$0.50/Matlab "How do I" query
$2.00/Matrix Problem
$5.00/10 minutes of coding help
$10.00/5 minutes of coding help for Walter's optimization project
Compiling ARPACK on Windows
27 February 2006 (08:21) -- I made these notes a while back, and thought I'd actually put them on the web.
1. Install MinGW and make sure to include the gcc/g77 and make utilities.
2. Edit ARmake.inc and change the following lines:
FC = g77
FFLAGS = -O2 -mno-cygwin
LDFLAGS =
CD = cd
LN = ln
LNFLAGS = -s
MAKE = /bin/make
RM = rm
RMFLAGS = -f
SHELL = /bin/sh
3. Compile ARPACK.
4. Run:
dllwrap --export-all-symbols -mno-cygwin --output-def arpack_win32.def -o arpack_win32.dll BLAS/*.o LAPACK/*.o UTIL/*.o SRC/*.o -lg2c
5. Using lib.exe in Visual Studio:
lib /machine:i386 /def:arpack_win32.def
6. Link your code against your new arpack_win32.lib file!
23 February 2006 (22:16)
The conference today was very interesting.
Talks I attended:
- Interior point methods for parallel linear programming.
- Solving linear programs with 10^9 variables.
- Iain Duff's presentation
- Yousef Saad's presentation.
- Introduction to Parallel Optimization
- Programming Techniques for Unstructured Data
- Out of core Grid Algorithms
- Dimensionality reduction for PDEs
- Support Graph Theory for Preconditioners
- Support Preconditions for FEM matrices.
- Support Preconditions for more FEM matrices.
- Steiner trees for Supporty Theory.
Much on preconditioning at the end there.
Still no ideas why the diameter esitmation isn't working.
Things I need to work on this weekend: reviewing papers; testing the copying model.
23 February 2006 (00:52)
Damn. There must be a bug in my diameter estimation code. (Or I don't really have a strongly connected component of my graph.) Time will tell.
23 February 2006 (00:43)
I'll update this page like a blog. Let's see how it works. Never expect anything and you won't be disappointed.