Wolf and Jolion’s Method for Binarization in Javascript

Wolf and Jolion’s method is a quite good one for image binarization and its code is online. There is a web demo of the method. In comparison with the original command line tool, it is somehow visualized, but the image size is limited.

Advertisements
Posted in Uncategorized | Leave a comment

Compile Calculix GraphiX (CGX) with MinGW

The Windows version of Calculix by bConvergent has not been updated long and CalculiX GraphiX (CGX) in CalculiXforWin is also quite old. It is somewhat easier to compile CCX and there are building guides about that online, so this blog is only about compiling CGX with MingW.

Missing headers and libraries

Some definitions in X Library are needed to deal with color maps, but some of those functions are never called by the main function. XFunktions.c and readStdCmap.c can be removed from Makefile.inc, and these lines below can be removed from cgx.c and extFunctions.c:

Display       *dpy;
int           dpycells;
Colormap      cmap;

The only definition really needed is that of Xcolor, so the line #include <GL/glx.h> in extUtil.h can be replaced with these lines copied from Xlib.h:

typedef struct {
    unsigned long pixel;
    unsigned short red, green, blue;
    char flags;  /* do_red, do_green, do_blue */
    char pad;
} XColor;

There is no dir.h in MinGW, but dirent.h can be a replacement. In readFoam.c and setFunktions.c, change #include <sys/dir.h> to #include <dirent.h> and struct direct *dp; to struct dirent *dp;.

There are still utsname and strtok_r needed. Implements of the two for Windows can be found on Internet.

Different definitions on Windows

Two variables in extFunktions.c conflict with dlgs.h included by windows.h, so these lines should be added to extFunktions.c:

#if defined(rad1)
    #undef rad1
#endif
#if defined(rad2)
    #undef rad2
#endif

GL_CLAMP_TO_EDGE is not defined in gl.h on Windows, so #include <GL/glext.h> should be added into extUtil.h.

GLUT

The GLUT provided with the source code of CGX can not be compiled on Windows, so remove those files from Makefile. Precompiled GLUT or FreeGLUT for Windows are easy to use. CGX with FreeGLUT 3.x will throw a “no display callback” error, so only lower version can be used.

LibSNL

The compilation of libSNL in Makefile can not work on Windows. Those files have to be compiled manually, but that is easy.

Read mode

Reading result file on demand does not work properly on Windows, so int read_mode=0; should be changed to int read_mode=1; in cgx.c.

Makefile

The last step is to make Makefile include and link correct files and some other modification to make things work.

Download

Of course, if you do not want to do all these yourself, the built files can be downloaded directly here, and here is a larger package containing CCX and some other useful binaries. All these are 32-bit and that is a reason for what I have to compile them myself.

Posted in Uncategorized | Tagged | 4 Comments

Unsolvability of General Quintic Equations and Higher

The unsolvability of general quintic equations and higher is a quite interesting problem, even for amateurs, and there are not a few books and articles to introduce this problem to amateurs. I had read quite a number of them and found those still too difficult to understand, until I found an very old book, Introduction to the Theory of Algebraic Equations by Leonard Eugene Dickson. It was published in 1903 and its explanation is very different from today’s. The first four chapters deal with this problem intuitively and make me understand this problem (or at least I feel I understand it) for the first time.

Posted in Uncategorized | Tagged | Leave a comment

The Methodist Mission in Jiujiang(Kiukiang), China

(If you can read Chinese, the Chinese version is recommended.)

The Methodist mission in Jiujiang (Kiukiang), China was sent by the Methodist Episcopal Church (abbr. MEC), a Northern American church and this mission played an important role in the modern history of Jiujiang City. Because of unifications with other Methodist churches, the name of this church changed to the Methodist Church in 1939 and now it is called the United Methodist Church. This article is written based on a few digitalized archives and the writer is not a Christian, so mistakes, including incorrect English usages, are certainly inevitable. If you have any information about this, please let me know.

Pinyin system, the current standard system in China Mainland, is adopted to romanize Chinese names and old spellings used by missionaries were put in parentheses. However, for some Chinese, their English names are used here, because those names were more commonly used in missionary documents than their Chinese ones, while their Chinese names are also given.


In 1847, MEC began its mission in China at Fuzhou (Foochow), the capital city of Fujian (Fukien) province. It resulted little for the first ten years and it took another ten years to make some progress in Fuzhou and nearby districts, then the church decided to expand its mission to other parts of China.

Dec. 1, 1867, Virgil Chittenden Hart (1840-1904) and Elbert S. Todd (1845-1919) arrived at Jiujiang, which began the Central China Mission of MEC. They arrived slightly earlier than missionaries sent to North China, so Jiujiang became the first station of MEC out of Fujian, and the Methodist mission was the first Protestant mission entering Jiujang. Rev. Hart was the Methodist pioneer of almost the entire Yangtze Valley and the building named after him still stands on the campus of Sichuan University, where formerly was the campus of West China Union University, a Christian university.

In 1869, for the first time a mission school was mentioned in the annual report of the mission in Jiujiang.

Nov. 13, 1872, Gertrude Howe (1846-1928) and Lucy H. Hoag (1844-1909) arrived at Jiujiang, who were sent by the Woman’s Foreign Missionary Society of the Methodist Episcopal Church (abbr. WFMS). A school for girls was open on the first day of the next year.

Dec. 1874, Letitia Mason (who married a Dr. Quine when no longer being a missionary), the first female medical missionary entering Yangtze Valley, after whom the hospital for women and children built at Zhenjiang (Chinkiang) later by MEC was named, arrived at Jiujiang. She did not work as a missionary long, but the medical work was carried on by several other medical women. It should be mentioned that one of them was Lucinda Combs Stritmatter (1849-1919), having arrived at Beijing (Peking) in 1873 as the first female medical missionary to China, who came to Jiujiang after she married a missionary in Jiujiang, Andrew Stritmatter (1847-1880).

In 1875, a medical missionary William E. Tarbell arrived at Jiujiang and he opened a dispensary in July, but he left just the next year. Since then, there was no male medical missionary of MEC in Jiujiang for a very long time, though there might be some foreign physicians helping the work in Jiujiang for MEC. Also in 1875, there was a riot against the missionary activities and chapels and schools of MEC inside of the Jiujiang City Wall were demolished. The indemnity for all the losses was paid by the local government.

At the end of 1876, Kiukiang Girl’s Boarding School of MEC moved to the southwest of Nengren Si (Ngn Ren Tsz), where the school, though have been merged with the boy’s school, still exists. After the relocation, the school was also called Mulberry Grove Academy.

At the beginning of 1881, Thomas C. Carter opened a boy’s high school, named Fowler University, to mark appreciation of the Secretary of the Missionary Society, Charles Henry Fowler (1837-1908). This school was one of the earliest general schools supplying English lessons in China. Rev. Carter was forced to leave by his falling health at the end of this year and newly-arrived Carl Frederick Kupfer (1852-1925) took charge of the school. Also in 1881, the mission began to build on Lushan for a sanitarium. Later on, two missionaries of MEC, Edward Selby Little (1864-1939) and John Reside Hykes (1852-1921), especially the first one, bought a lot of land on that mountain to develop and made it one of the most famous summer resorts, with the name Kuling given by Rev. Little.

In 1882, female medical missionaries in Jiujiang left and no more people succeeded, so the medical work of WFMS in Jiujiang discontinued.

In 1883, the only missionary of WFMS then, Miss Howe conflicted with male missionaries and she resigned and left. However, she went to Chongqing (Chung-king) and worked there for WFMS. Her work at Jiujiang was taken by wives of male missionaries.

In 1884 or 1885, Fowler University moved to the new site near the south gate of the City Wall, by the side of the Girl’s Boarding School, where the school still exists, and the quite imposing “University” was changed to “Institute”.

In 1886, a riot against Christian missions happened in Chongqing. Missionaries of MEC there retreated to Jiujiang, when the confliction between Miss Howe and male missionaries seemed to be vanished and she worked at Jiujiang again.

In 1888, Bishop Fowler (elected to the Episcopacy in 1884), who came to China to supervise the missions in China, thought it was improper to name the boy’s school at Jiujiang after his own name and changed its name to Kiukiang Institute.

In 1889, two Chinese students Hu Qibing (Hu Chi-ping) and Yü Kaizhi (Yü Kai-chi) went to Germany to study in the Methodist Mission Institute at Frankfurt, probably the first to study abroad from Jiujiang. Hu Qibing graduated in 1893 and Yü Kaizhi unfortunately died there in 1894.

In 1893, Kate Louise Ogborn (1862-1932) opened a Woman’s Bible Training School.

In 1896, Ida Kahn (1873-1931, Chinese name: Kang Aide or Kang Cheng), an adopted daughter of Miss Howe, and Mary Stone (1873-1954, Chinese name: Shi Meiyu), a daughter of one of the first native pastors of the Central China Mission, graduated from the Medical School of Michigan University. They had probably never been in America before they went to the university four years ago, but their grades were always leading their class. They returned to Jiujiang in the fall and a dispensary was erected before the end of the year. These two of the earliest female graduates from Western countries came back when the Chinese reformists were advocating woman’s education and these two young doctors were widely introduced as the new models of Chinese women.

Early in 1901, Kiukiang Institute was renamed to William Nast College, to memorialize William Nast (1807-1899), the founder and leader of German-American Methodism, in recognition of large contributions to this school from German-American Methodism. Rev. Kupfer, who had once been the president and who was from a German-American Conference, served as the president again. Only two years’ courses were supplied at the beginning and courses were like those in colleges in America in 1905, but after all this school could hardly be called a real college.

Dec. 7, 1901, Danforth Memorial Hospital for women and children opened formally, funded by Dr. Isaac Newton Danforth (1835-1911) of Chicago to memorialize his wife Elizabeth Skelton Danforth (1843-1895) and supervised by Dr. Kahn and Dr. Stone. The hospital still stands at its original site with some old buildings.

About 1903, some female missionaries in Jiujiang were appointed to Nanchang. Miss Ogborn opened Baldwin Memorial High School for Girls and Dr. Kahn opened a dispensary, which was later turned into Nanchang Woman’s and Child’s Hospital.

About 1905, the Girl’s Boarding School was renamed after Sally Ann Rulison-Fish (1833-1902), who was a famous organizer of missionary societies and publisher of missionary periodicals then in Michigan. Sep. 1907, the new school building opened to receive students, and this building still stands.

About 1907, the Woman’s Bible Training School was named after Ellin J. Knowles (1834-1929) and in 1911, the new school was ready for students. Its site was opposite to Danforth Hospital, but now no evidence of that school can be found there.

In 1909, a Chinese, Yu Facheng was struck in the British Concession in Jiujiang by a policeman and died. Native Methodists tried to help the victim with their knowledge about foreign affairs and the Superintendent of Methodist Wuhu Hospital, Dr. Edgerton Haskell Hart (1868-1913), born at Jiujiang to Rev. Virgil Hart, was invited to Jiujiang to examine the body. It was stated in his report that the death was caused by the injury of the blows, but his testimony was discounted by the British Consul and the policeman was released for there was no sufficient evidence.

In 1912, Kiangsi Mission was separated from the Central China Annual Conference and in 1917, it was elevated to an annual conference.

In 1918, under the special condition of World War I, Rev. Kupfer, the President of William Nast College, was accused for his pro-German disloyalty. The church ordered him to retire and German and German-American people in this college was forced to leave. The plan of the college was also reduced, and it turned to be just a high school in 1920. After the school was degraded, some better-educated native teachers left. Yet the name “College” had not been changed until about 1928, when it was renamed to William Nast Academy.

Sep. 20, 1918, Edward Carter Perkins (1875-1958) opened Water of Life Hospital. Its name was from the sentence he loved, “Whosoever will, let him take of the water of life freely.” The fund of building and maintaining the hospital was mainly from Dr. Perkins himself. Only men were received at the beginning because there had been Danforth Hospital for women, but after 1936 women could also come to this hospital while obstetrical cases should be turned to Danforth Hospital. This hospital now is the largest hospital in Jiujiang, at the place where it was founded. The old main building of the hospital and Dr. Perkins’ house still exists.

In 1920, Dr. Stone, the Superintendent of Danforth Hospital, and Jennie V. Hughes (1874-1951), the Principal of Knowles Woman’s Bible Training School, conflicted with the board of WFMS. They resigned and went to Shanghai to found Bethel Church. Not a small part of the staff of the hospital and the school left with them.

In 1927, it was demanded by the Chinese government that heads of schools must be Chinese. Cai Degao (Tsai Teh-kao) was appointed the first Chinese Principal of William Nast College, and Xiong Xiangxi (Hsiung Chiang-hsu) succeeded him in the next year. Hu Zihua (Hu Tze-hwa) was appointed the first Chinese Principal of Rulison-Fish School, and Grace Wu (Chinese name: Wu Maocheng) succeeded her in the next year. Rev. Xiong and Miss Wu headed the two schools long until early 1950’s. Beatrice Lee (Chinese name: Li Zhemin) was appointed the Principal of Knowles Woman’s Bible Training School, of which the younger sister of Dr. Stone, Anna Stone (1880-1906, Chinese name: Shi Anli), had been the principal before. Also in 1927, the primary department of William Nast College moved to Taling Street and became an independent school, William Nast Primary School. This school does not exist but one building is left.

In 1938, because of the invasion of Japan, William Nast Academy moved to Dingjia’ao, Bishan, Sichuan (Tin-chia-ngao, Pi-shan, Sze-chwan) and Rulison-Fish School moved to Zizhong (Tze-chung), Sichuan, then to Suining the next year, where it collaborated with a part of Baldwin School which also came here and the local Methodist girl’s school, forming an associated school. The part of these two schools left in Jiujiang and Knowles Woman’s Bible Training School were associated.

In 1939, three large Methodist churches in America, Methodist Episcopal Church and Methodist Episcopal Church, South and Methodist Protestant Church were united to be the Methodist Church.

After the Pacific War broke out in 1941, Americans in the territory occupied by Japanese were interned. These people were repatriated to America in the next years, exchanged with interned Japanese and institutions owned by them were occupied by Japanese. When the war ended, Methodist schools moved back and hospitals opened again.

In 1949, the Communist army crossed Yangtze River and the new government tightened the restriction against missionaries gradually. At the end of 1950, after America and China went to war, Methodist missionaries in Jiujiang were ordered to leave by the local government. These last missionaries were Mabel A. Woodruff, Dr. & Mrs. Perkins, Annie May Pittman, Deanetta & Elizabeth Ploeg (perhaps the list is not a complete one). In 1951, Methodist schools and hospitals were nationalized by the government and soon Rulison-Fish School was merged with William Nast Academy. The Methodist Church in China Mainland survived several years more, then it was absorbed into “Three-Self” Church, the official Protestant church in 1958.


The heads of schools and hospitals built by the Methodist mission in Jiujiang are listed below, though these lists are not complete obviously.

Principal of Rulison-Fish School for Girls

1873~1883 Gertrude Howe*
1883~1886 Lydia Krill Kupfer(Carl Frederick Kupfer’s wife)
1886~1898 Gertrude Howe*
1898~1927 Clara E. Merrill
1927~1928 Hu Zihua
1928~1951 Grace Wu

* At most times, more than one missionary supervised the educational work for girls in Jiujiang and it is not clear which one was the head of this school. Miss Howe is put in the table only because she served long in Jiujiang.

Principal of William Nast Academy

1881 Thomas C. Carter
1881~1888 Carl Frederick Kupfer
1888~1899 James Jackson
1899~1901 Jesse F. Newman
1901~1918 Carl Frederick Kupfer
1918~1920 Vacancy*
1920~1927 Charles F. Johannaber
1927~1928 Cai Degao
1928~1951 Xiong Xiangxi

* George Carleton Lacy, Edward Carter Perkins and Hu Qibing served as the acting one successively.

Principal of Knowles Woman’s Bible Training School

1893~1903 Kate Louise Ogborn
1903~1906 Anna Stone
1906~1920 Jennie V. Hughes
1920~1922 Mabel A. Woodruff
1922~1927 May Bel Thompson
1927~1934 Beatrice Lee

Superintendent of Danforth Hospital

1901~1903 Ida Kahn and Mary Stone
1903~1920 Mary Stone
1920~1921 Vacancy (Acting Superintendent: Chen Yuzhen (Chen Yu-chen) )
1921~1924 Zou Bangyuan (Tseo Pang-yuen)
1924~1934 Chen Yuzhen

Superintendent of Water of Life Hospital

1918~1942 Edward Carter Perkins
1946~1950 Edward Carter Perkins
Posted in History | Tagged , | Leave a comment

Fill-reducing for regular 9-point stencil grid

When using 9-point stencil finite difference or finite element method, every vertex has 8 neighbors except ones on the boundary. In the picture in previous blog, every smallest square is a clique in 9-point grid. Regular 9-point grid is what Nested Dissection was invented for originally[1]. 5-point grid and 9-point grid are quite different for fill-reducing. As the benchmark shows, MESHND performs very well except the very small grids for 9-point grid. Though MESHND is so good in this condition, further improvement can be achieved.
9-point grid
For fill-reducing, minimal separators are essential[2]. Original Nested Dissection, which MESHND implemented, uses horizontal or vertical lines as separators and for every subgraph, heuristically the line dividing the subgraph equally is chosen. Considering MESHND is so good for 9-point grid, it is acceptable to restrict the separators to be horizontal or vertical lines. But it is better to choose the line resulting minimum fill-in directly.

In the grid, a rectangle C_0, whose neighbor is S_0, can be separated into two smaller rectangles C_1 and C_2 by a horizontal or vertical line S. Compared with fill-in, nonzeros in the factorization can be calculated more straightforward. The minimum nonzeros of C_0
\mathrm{mnz}(C_0) = \min_S \left(\mathrm{nz}(S)+\mathrm{mnz}(C_1)+\mathrm{mnz}(C_2)\right)
\mathrm{nz}(S) is the nonzeros of S
\mathrm{nz}(S) = \mathrm{tr}\left(|S_0|+|S|\right)-\mathrm{tr}\left(|S_0|\right)
where \mathrm{tr}(n) means the n\mathrm{th} triangular number(the sum of natural numbers from 1 to n). This is based on an observation, off-diagonal nonzeros is the surrounding vertices ordered after the vertex. This definition of surrounding depends on the connection. For example, in the ordering below, for 5-point grid, off-diagonal nonzeros of Vertex 20 are {40,43,45,49}, and for 9-point grid, they are {21,29,30,40,41,42,43,44,45,46,47,48,49}. When S is in the neighbor of S_0, it is not a separator of C_0 and the above formulas can not be applied directly. In this special case, at least one smaller rectangle is empty and \mathrm{nz}(S) is not difficult to calculate with the observation. Nonzeros of a rectangle is only determined by it width, height and the shape of its neighbor and there are only a few different shapes of the neighbor of a rectangle. For s\times t grid, all the rectangles k\times l, k\leq s, l\leq t need to be computed. k\times l rectangle has k+l horizontal or vertical lines. So the time complexity of this method is \mathcal{O}(s^2 t+t^2 s). Further details can be seen in the code of the demo. When the grid is large, it costs a lot of DOM operations to display the ordering. To save time, mnz(s,t,0,0) can be called to return the minimum nonzeros of s&timest grid in the JavaScript console if it is not necessary to display the ordering.

Table 1. An ordering of 7×7 grid
23 24 41 2 7 5 3
25 26 42 8 9 6 4
27 28 21 43 1 47 48
22 39 40 20 45 17 11
38 37 29 49 10 18 16
33 34 36 44 19 15 13
31 32 35 30 46 14 12

This method can be extended to more general case. C_0 can be any component and S is its separator. The object can be changed to operations in the factorization, which is the quadratic sum of nonzeros of all vertices. This is also included in the demo, though commented out. Minimizing operations leads to a different ordering but it will not be discussed here.

The ordering shown in the demo is only one of many cases resulting minimum fill-in. When the grid is very small, AMD is better than MESHND. But the method proposed here surpasses both methods in all cases I have tested(Table 2, Table 3). The improvement over MESHND is very small (only 3-4 percent) for large square grid(Table 2). So in this case where Nested Dissection originate, though dividing the graph equally is not the best choice, it is only little worse than the best choice.

Table 2. Nonzeros of s×s grid
s AMD Metis MESHND Proposed Method
7 3.29E+02 3.50E+02 3.54E+02 3.18E+02
15 2.65E+03 2.95E+03 2.78E+03 2.61E+03
31 1.75E+04 1.97E+04 1.77E+04 1.69E+04
63 1.02E+05 1.10E+05 9.95E+04 9.56E+04
127 5.73E+05 5.65E+05 5.19E+05 5.00E+05
255 3.24E+06 2.76E+06 2.57E+06 2.48E+06
511 1.70E+07 1.36E+07 1.23E+07 1.19E+07
1023 8.55E+07 6.12E+07 5.72E+07 5.54E+07

When the grid is not square, the improvement is more significant as the aspect ratio increases(Table 3). It is interesting that relative difference between AMD and MEHSND also becomes larger as the aspect ratio increases(Table 3).

Table 3. Nonzeros of 31×s grid
s AMD Metis MESHND Proposed Method
63 4.06E+04 4.56E+04 4.12E+04 3.91E+04
127 8.68E+04 9.87E+04 9.01E+04 8.39E+04
255 1.79E+05 2.11E+05 1.90E+05 1.74E+05
511 3.64E+05 4.31E+05 3.91E+05 3.53E+05
1023 7.33E+05 7.96E+05 7.96E+05 7.12E+05

The minimum fill-in of s\times s grid is \mathcal{O}\left(s^2 \log s\right)[3]. Regressing the result of this method, the minimum fill-in of s\times t grid may be \mathcal{O}\left(st\log\left(\min(s,t)\right)\right). As pointed out, AMD is a good complement for Nested Dissection, not only when the grid is too small, but also when the grid is too slim. I suppose that the distance is important for fill-reducing, not only the size. A square is a disc for 9-point grid. In Nested Dissection, a disc is split into 4 smaller discs and every smaller disc is further split, which produces very good result. When the shape is different, maybe some other skills can be added to improve the result.

References
[1] A. George, Nested dissection of a regular finite-element mesh.
[2] V. Bouchitté, I. Todinca, Treewidth and minimum fill-in grouping the minimal separators.
[3] A. George, J. Liu, E. Ng, Computer Solution of Sparse Linear Systems.

Posted in Sparse matrix | Tagged , , | Leave a comment

Fill-reducing for regular 5-point stencil grid

Fill-reducing is key to sparse matrix factorization. This course contains a very good introduction to this topic. This course is much earlier but still useful. And George & Liu’s book on sparse linear systems can be downloaded there. Minimum of fill-in is an NP-complete problem. There are two major heuristic method, minimum degree and nested dissection. AMD and Metis are two popular packages corresponding to these two methods. AMD and its variants are contained in Matlab. Metis can be used in Matlab with this mex interface.
5-point grid
What I concern is a special case, square grid(above). There is a Matlab package MESHND for nested dissection in this simple case. Its benchmark shows it does not perform well for 5-point stencil. I thought there should be some simple and efficient method for this simple symmetric case. I tried to use constrained AMD(CAMD) with some proper constraint to improve the result. I found that eliminating four triangle in Picture A below first will produce a better result. I contacted with Bora Uçar, and he suggested to use more diamonds to partition the grid, like Picture B.The method finds out the borders and constrain them to be ordered later in CAMD. This does further improve the result, though the best number of diamonds is not easy to determine. Borders of diamonds are circles under the distance defined by the connection of 5-point stencil.They separate the domain with the minimal size. Under the condition of 9-point stencil, circles turn out to be squares in Picture C. This is the way MESHND partitions the grid.
However, the size of separators just partially explain the result. This becomes obvious when this method is extended to 3D 7-point stencil case. In 3D, the best shape for the size of separators is truncated octahedron. But those truncated octahedra are not good for fill-reducing. The best method I found is simply extending 2D diamonds to 3D. They become octahedra. Octahedra can not fill the 3D domain like diamonds in 2D (ignoring boundaries). There leaves many tetrahedra. These separators are not optimized in size, but they are much more suitable for fill-reducing. The Matlab code to generate the constraint in this way for CAMD is here. 2D version can be easily reduced from that.
fill-reducing
Here is a comparison among different methods on s×s regular 5-point stencil grid.

Nonzeros in the Cholesky factorization(2D grid, 5-point stencil)
s MESHND AMD Metis Proposed Method
64 8.81E+004 6.72E+004 7.06E+004 6.19E+004
128 4.62E+005 3.81E+005 3.51E+005 3.02E+005
256 2.32E+006 1.97E+006 1.57E+006 1.45E+006
512 1.12E+007 9.90E+006 7.83E+006 6.76E+006
1024 5.27E+007 4.75E+007 3.75E+007 3.11E+007

There are 4 diamonds per row like picture B above for s=64,128,256. And this number turns out to be 8 when s=512,1024. As a general method, Metis performs well, but it costs much more time than the others.
And for 3D s×s×s grid, the number of nonzeros by this method is as good as the result of Metis, while Metis is much slower and its memory consumption is much higher. Metis runs out of memory on my Win32 machine when s=128.

Nonzeros in the Cholesky factorization(3D grid, 7-point stencil)
s MESHND AMD Metis Proposed Method
16 3.86E+005 2.81E+005 2.21E+005 2.54E+005
24 2.32E+006 1.87E+006 1.52E+006 1.49E+006
32 8.11E+006 7.75E+006 5.52E+006 5.18E+006
48 4.63E+007 5.23E+007 2.71E+007 2.90E+007
64 1.57E+008 1.84E+008 9.55E+007 9.89E+007
128 2.83E+009 5.17E+009 NA 1.91E+009

If you have any better explanation or better method, please let me know.
Continue reading

Posted in Sparse matrix | Tagged , , | Leave a comment

Compile Metis 5 with MinGW

I tried to compile files manually and found only two points are needed.

  • Comment out or delete the line #include <sys/resource.h> in gk_arch.h.
  • Add 2 command options for GCC: -std=c99 and -DUSE_GKREGEX.

If CMake is used, only the first is necessary.

Posted in Sparse matrix | Tagged , | 8 Comments